このテクは勉強になった。
https://codeforces.com/contest/1181/problem/E2
問題
グリッド上にN個の矩形領域が与えられる。
これらの領域は重複はしていないが、全領域の和をとってもグリッド全体になるとは限らない。
グリッドをN個の長方形に分割したとき、これらの矩形が1個ずつ入るようにできるか。
解法
基本的には、複数の矩形領域が含まれる長方形があったら、どこか縦か横に二分割して分離していく、という方針。
ただうまく分割位置を探さないと、O(N^2)かかりかねない。
そこで分割位置の探し方だが、上から下や左から右の一方通行ではなく、上下左右4方向から徐々に狭めていく。
こうすると分割する際に、探索時間が長いほど均等に二分割され今後の探索が高速になる。
int N; int X1[101010],X2[101010],Y1[101010],Y2[101010]; int dfs(set<pair<int,int>>& L, set<pair<int,int>>& R,set<pair<int,int>>& U,set<pair<int,int>>& D) { if(L.size()<=1) return 1; auto Lit=L.begin(); auto Rit=R.begin(); auto Dit=D.begin(); auto Uit=U.begin(); int Llim=X2[Lit->second]; int Rlim=X1[Rit->second]; int Dlim=Y2[Dit->second]; int Ulim=Y1[Uit->second]; set<pair<int,int>> L2,R2,U2,D2; while(1) { Lit++; Rit++; Dit++; Uit++; if(Lit==L.end()) break; if(Lit->first>=Llim) { auto p=*Lit; while(*L.begin()!=p) { int x=L.begin()->second; L2.insert({X1[x],x}); R2.insert({-X2[x],x}); D2.insert({Y1[x],x}); U2.insert({-Y2[x],x}); L.erase({X1[x],x}); R.erase({-X2[x],x}); D.erase({Y1[x],x}); U.erase({-Y2[x],x}); } return dfs(L,R,U,D)&&dfs(L2,R2,U2,D2); } if(Dit->first>=Dlim) { auto p=*Dit; while(*D.begin()!=p) { int x=D.begin()->second; L2.insert({X1[x],x}); R2.insert({-X2[x],x}); D2.insert({Y1[x],x}); U2.insert({-Y2[x],x}); L.erase({X1[x],x}); R.erase({-X2[x],x}); D.erase({Y1[x],x}); U.erase({-Y2[x],x}); } return dfs(L,R,U,D)&&dfs(L2,R2,U2,D2); } if(-Rit->first<=Rlim) { auto p=*Rit; while(*R.begin()!=p) { int x=R.begin()->second; L2.insert({X1[x],x}); R2.insert({-X2[x],x}); D2.insert({Y1[x],x}); U2.insert({-Y2[x],x}); L.erase({X1[x],x}); R.erase({-X2[x],x}); D.erase({Y1[x],x}); U.erase({-Y2[x],x}); } return dfs(L,R,U,D)&&dfs(L2,R2,U2,D2); } if(-Uit->first<=Ulim) { auto p=*Uit; while(*U.begin()!=p) { int x=U.begin()->second; L2.insert({X1[x],x}); R2.insert({-X2[x],x}); D2.insert({Y1[x],x}); U2.insert({-Y2[x],x}); L.erase({X1[x],x}); R.erase({-X2[x],x}); D.erase({Y1[x],x}); U.erase({-Y2[x],x}); } return dfs(L,R,U,D)&&dfs(L2,R2,U2,D2); } Llim=max(Llim,X2[Lit->second]); Rlim=min(Rlim,X1[Rit->second]); Dlim=max(Dlim,Y2[Dit->second]); Ulim=min(Ulim,Y1[Uit->second]); } return 0; } int dfs(vector<int>& A) { if(A.size()<=1) return 1; int i,R; vector<pair<int,int>> C; //X FORR(a,A) C.push_back({X1[a],X2[a]}); sort(ALL(C)); R=C[0].second; for(i=1;i<C.size();i++) { if(C[i].first>=R) { vector<int> S,T; FORR(a,A) { if(X2[a]<=C[i].first) S.push_back(a); else T.push_back(a); } return dfs(S)&dfs(T); } else { R=max(R,C[i].second); } } C.clear(); // Y FORR(a,A) C.push_back({Y1[a],Y2[a]}); sort(ALL(C)); R=C[0].second; for(i=1;i<C.size();i++) { if(C[i].first>=R) { vector<int> S,T; FORR(a,A) { if(Y2[a]<=C[i].first) S.push_back(a); else T.push_back(a); } return dfs(S)&dfs(T); } else { R=max(R,C[i].second); } } return 0; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; set<pair<int,int>> L,R,U,D; FOR(i,N) { cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i]; L.insert({X1[i],i}); R.insert({-X2[i],i}); D.insert({Y1[i],i}); U.insert({-Y2[i],i}); } if(dfs(L,R,U,D)) _P("YES\n"); else _P("NO\n"); }
まとめ
似たテク他にもどこかで見た気がするんだよなー。