Codeforces ECR #072 : F. Forced Online Queries Problem

まぁ教育的といえば教育的だが。
https://codeforces.com/contest/1217/problem/F

問題

N頂点のグラフがあり、初期状態で辺はない。
以下のQ個のクエリに順次答えよ。
なお、クエリの指す頂点対の番号は、直前の後者の結果がTrueの場合、1ずれる。

• 指定された頂点対の間に辺を張る。すでに張られている場合削除する。
• 頂点対が連結が答える。

解法

平方分割と巻き戻し可能なUnion-Findで解く。
平方分割ということで、クエリを√Qごとにブロックを分け解いていこう。
すでに張られた辺のうち、ブロック内で更新される可能性のない辺を、先に巻き戻し可能なUnion-Findで連結させる。
最後に更新の可能性がある辺を連結させる。

クエリは一見オンラインだが、頂点番号は高々1しかずれないので、可能性のある辺の数はそう多くない。
あとは各クエリに答えていくわけだが、連結処理は高々√Q個しか巻き戻しが生じないので間に合う。

int N,Q,last;
int T[202020],X[202020],Y[202020];

template<int um> class UF_pop {
	public:
	vector<int> par,rank; vector<vector<int>> hist;
	UF_pop() {par=rank=vector<int>(um,0); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; hist.clear(); FOR(i,um) rank[i]=0,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):operator[](par[x]);}
	void pop() {
		if(hist.size()) {
			auto a=hist.back();
			hist.pop_back();
			par[a[0]]=a[1]; rank[a[0]]=a[2];
			par[a[3]]=a[4]; rank[a[3]]=a[5];
		}
	}
	void operator()(int x,int y) {
		x=operator[](x); y=operator[](y);
		hist.push_back({x,par[x],rank[x],y,par[y],rank[y]});
		if(x==y) return;
		if(rank[x]<rank[y]) par[x]=y;
		else rank[x]+=(rank[x]==rank[y]), par[y]=x;
	}
};

const int DI=1200;
UF_pop<200020> uf;
pair<int,int> p(int a,int b) { return {min(a,b),max(a,b)};};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,Q) {
		cin>>T[i]>>X[i]>>Y[i];
		X[i]--,Y[i]--;
	}
	
	set<pair<int,int>> S;
	string R;
	
	for(int start=0;start<Q;start+=DI) {
		set<pair<int,int>> A=S,B;
		vector<pair<int,int>> V;
		uf.reinit();
		for(i=start;i<min(start+DI,Q);i++) {
			if(T[i]==1) {
				if(A.count(p(X[i],Y[i]))) {
					A.erase(p(X[i],Y[i]));
					B.insert(p(X[i],Y[i]));
				}
				if(A.count(p((X[i]+1)%N,(Y[i]+1)%N))) {
					A.erase(p((X[i]+1)%N,(Y[i]+1)%N));
					B.insert(p((X[i]+1)%N,(Y[i]+1)%N));
				}
				
			}
		}
		FORR(a,A) uf(a.first,a.second);
		FORR(b,B) {
			V.push_back(b);
			uf(b.first,b.second);
			
		}
		for(i=start;i<min(start+DI,Q);i++) {
			X[i]+=last;
			X[i]%=N;
			Y[i]+=last;
			Y[i]%=N;
			if(T[i]==1) {
				
				if(B.count(p(X[i],Y[i]))) {
					B.erase(p(X[i],Y[i]));
					S.erase(p(X[i],Y[i]));
					vector<pair<int,int>> T;
					while(1) {
						uf.pop();
						if(V.back()==p(X[i],Y[i])) {
							V.pop_back();
							break;
						}
						else {
							T.push_back(V.back());
							V.pop_back();
						}
					}
					FORR(t,T) {
						V.push_back(t);
						uf(t.first,t.second);
					}
				}
				else {
					B.insert(p(X[i],Y[i]));
					S.insert(p(X[i],Y[i]));
					V.push_back(p(X[i],Y[i]));
					uf(X[i],Y[i]);
				}
				
			}
			else {
				last=uf[X[i]]==uf[Y[i]];
				R+='0'+last;
			}
			
		}
	}
	cout<<R<<endl;
	
	
}

まとめ

オンラインで処理する問題なんだけど、オンラインのさせ方にバリエーションが小さいことを使う、というヘンテコな問題。