AtCoderだと出なそうな問題?
https://codeforces.com/contest/1214/problem/G
問題
H*Wのグリッドがあり、初期状態では全セル緑である。
ここで、Q個のクエリが与えられる。
各クエリでは、1つの行における連続したセルの色が青・緑反転される。
各クエリ後、矩形のうち左上と右下セルの色が一致し、右上と左下セルの色が一致し、ただし両者の色は異なるような矩形を1つ答えよ。
解法
R[y] := y列目のうち青色の列をbitsetで管理したもの
とする。R[a]⊂R[b]ではなくR[b]⊂R[a]でもないような列の対a,bがあれば、両者のxorを取ると2つ以上1のbitが立つので、それらの列・行を答えればよい。
とはいえ毎回a,bを総当たりすると間に合わない。
ここで、bitの立っている列の数が昇順になるように行を並べ、隣接行とだけ比較するようにしよう。
クエリ1回毎には数行分しか比較しないのでなんとか間に合う。
bitset<2020> R[2020],pref[2020]; int H,W,Q; set<pair<int,int>> cand; bitset<2020> ans; int P[2020]; void check(int l,int r) { if(l<0 || r>=H) return; if((R[l]|R[r])!=R[r]) { P[l]=r; ans.set(l); } } void del(int y) { P[y]=-1; ans.reset(y); int c=R[y].count(); auto it=cand.find({c,y}); auto lef=it,rig=it; lef--;rig++; int le=lef->second; int ri=rig->second; cand.erase(it); if(le>=0 && P[le]>=0) P[le]=-1, ans.reset(le); check(le,ri); } void ins(int y) { int c=R[y].count(); cand.insert({c,y}); auto it=cand.find({c,y}); auto lef=it,rig=it; lef--;rig++; int le=lef->second; int ri=rig->second; if(le>=0 && P[le]>=0) P[le]=-1, ans.reset(le); check(le,y); check(y,ri); } void solve() { int i,j,k,l,r,x,y; string s; MINUS(P); scanf("%d%d%d",&H,&W,&Q); FOR(y,2010) FOR(x,y) pref[y].set(x); cand.insert({-1,-1}); cand.insert({W+1,H}); FOR(y,H) cand.insert({0,y}); while(Q--) { int A,l,r; scanf("%d%d%d",&A,&l,&r); A--; del(A); R[A]^=pref[r]; R[A]^=pref[l-1]; ins(A); if(ans.count()==0) { _P("-1\n"); } else { int y1=ans._Find_first(); int y2=P[y1]; if(y1>y2) swap(y1,y2); int x1=(R[y1]&~R[y2])._Find_first(); int x2=(R[y2]&~R[y1])._Find_first(); if(x1>x2) swap(x1,x2); _P("%d %d %d %d\n",y1+1,x1+1,y2+1,x2+1); } } }
まとめ
なんかECRみたいな問題。
bitset押しのせいかな。