Codeforces #583 G. Feeling Good

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押しのせいかな。