Codeforces #657 Div2 F2. Chess Strikes Back (hard version)

よくこういう問題考えつくなぁ。
https://codeforces.com/contest/1379/problem/F2

問題

2N*2Mの市松模様に塗られたチェス盤を考える。
このうち白マスを1つ選んで使用不可にするまたは使用不可を解除するクエリが与えられる。
各クエリの実行後、下記を答えよ。

• 白マス2NM個中、使用可能なマスにNM個キングの駒を置く。互いに1手で取れるような関係にしない置き方ができるか。

解法

2*2のマスからなるグループがN*M個並んでいると考える。
各グループにはキングは1個ずつ置かなければいけないことになる。
グループ内で、左上にキングを置くグループと右下にキングを置くグループがあるとすると、前者は後者の左上にないといけない。

そこで、各行において、

• 左上にキングを置かざるを得ない一番右のグループ
• 右下にキングを置かざるを得ない一番左のグループ

を管理し、上記条件の違反の有無を更新しよう。

const int NV=1<<20;
int A[NV*2],B[NV*2],C[NV*2];

int N,M,Q;
multiset<int> L[202020],R[202020];
set<pair<int,int>> P;

void update(int entry) {
	entry += NV;
	if(L[entry-NV].empty()) {
		A[entry]=1<<20;
	}
	else {
		A[entry]=*L[entry-NV].begin();
	}
	if(R[entry-NV].empty()) {
		B[entry]=-1;
	}
	else {
		B[entry]=*prev(R[entry-NV].end());
	}
	C[entry]=A[entry]<=B[entry];
	
	while(entry>1) {
		entry>>=1;
		C[entry]=C[entry*2] | C[entry*2+1] | (A[entry*2]<=B[entry*2+1]);
		A[entry]=min(A[entry*2],A[entry*2+1]);
		B[entry]=max(B[entry*2],B[entry*2+1]);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>Q;
	
	FOR(i,2*NV) {
		A[i]=1<<20;
		B[i]=-1;
		C[i]=0;
	}
	
	
	int NF=0;
	while(Q--) {
		cin>>y>>x;
		y--;
		x--;
		int r=y%2;
		y/=2;x/=2;
		
		if(P.count({y,r*1000000+x})) {
			P.erase({y,r*1000000+x});
			
			if(r==0) {
				L[x].erase(L[x].find(y));
			}
			else {
				R[x].erase(R[x].find(y));
			}
		}
		else {
			P.insert({y,r*1000000+x});
			if(r==0) {
				L[x].insert(y);
			}
			else {
				R[x].insert(y);
			}
		}
		update(x);
		if(C[1]) {
			cout<<"NO"<<endl;
		}
		else {
			cout<<"YES"<<endl;
		}
		
		
	}
	
}

まとめ

結果だけ聞いちゃうと、Easyの存在意義がよくわからんな。
どういう解法を想定したのだろう。