Selection Contest for Rookies 1 F Forced Online Queries Problem

考虑并查集按秩合并和暴力撤销 可以维护加边和删边的操作

考虑分块 详见 https://blog.csdn.net/weixin_44231553/article/details/100598481

时间复杂度 O(q*sqrt(q)*logn) 调一调参数可以过

我就是来贴个代码

#include
 
using namespace std;
 
#define N 200005
#define B 5000
 
int f[N], sz[N], st[N][3], top, bot, n, q, i, L, R, j, ans[N], t[N], x, y, px, py;
set > a, b, c;
pair e;
pair E[N][2];
 
int find(int x)
{
	return x==f[x]?x:find(f[x]);
}
 
void addc(int x,int y)
{
	x=find(x),y=find(y);
	if (x==y) return;
	if (sz[x]y) swap(x,y);
			E[j][0]=make_pair(x,y);
			x=x%n+1;
			y=y%n+1;
			if (x>y) swap(x,y);
			E[j][1]=make_pair(x,y);
			a.insert(E[j][0]);
			a.insert(E[j][1]);
		}
		for (j=1; j >::iterator x=c.begin(); x!=c.end(); x++) {
        	px=(*x).first;
        	py=(*x).second;
        	addc(px,py);
		}
		top=bot=0;
		for (j=L; j<=R; j++) {
			if (t[j]==1) {
				ans[j]=ans[j-1];
				e=E[j][ans[j]];
				if (b.find(e)==b.end()) b.insert(e);
				else b.erase(e);
			}
			else {
				e=E[j][ans[j-1]];
				while (top!=bot) {
					sz[st[top][0]]=st[top][1];
					f[st[top][2]]=st[top][2];
					top--;
				}
		        for (set >::iterator x=b.begin(); x!=b.end(); x++) {
		        	px=(*x).first;
		        	py=(*x).second;
		        	addb(px,py);
				}
				ans[j]=find(e.first)==find(e.second);
			}
		}
	}
	for (i=1; i<=q; i++) if (t[i]==2) printf("%d",ans[i]);
 
	return 0;
}