题解 | #Graph Games#

题目链接

第一眼看上去不太可做，因为两个集合相同必须满足其中所有元素都相同，而我们无法直接处理这样的信息。

但我们可以抓住「集合是无须的」，使用一种名为 XOR Hashing 的 Trick 来解决这个问题。

这里放上 CF 原博客链接 link

具体而言，就是我们只关心哪些元素出现了而不关心其顺序，可以用随机数（或者自然溢出）哈希的方式，结合 XOR 运算，形成一种「可逆」的哈希。

在本题中，给每个节点一个哈希值 $w (x)$ ，维护每个 $S (x)$ 的哈希值。如果 $(x, y)$ 这条边被删除了，那么就把 $w (y)$ 异或掉。这样一定能得到准确的每个 $S (x)$ 的信息。

如何快速修改呢？一个边区间可能对很多点产生贡献，线段树不太好写，考虑分块。

在 $[1, M]$ 上分块。首先定义 $v (x)$ 为 $S (x)$ 的哈希值异或和。

对于散块上的一点 $(x, y)$ ，直接让 $v (x)$ 异或上 $w (y)$ ， $v (y)$ 异或上 $w (x)$ ，除掉对方的哈希值。

对于整块，由于异或运算满足交换律，所以可以将散块的贡献与整块的贡献分开，如果修改了整块，那么直接修改整块的状态即可。查询的时候， $v (x)$ 一定是初始异或和减掉散块的贡献，此时如果某一个整块的状态是被删除，那么就让其再异或上这一块对 $x$ 的贡献即可。如何预处理？设 $d (p, x)$ 表示第 $p$ 块对 $x$ 的贡献，对于第 $i$ 条边 $(x, y)$ ，让 $d (p o s [i], x)$ 异或上 $w (y)$ ，反过来再做一次即可。

如此，只要判断是否相等即可。

#include<bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define SET(a,b) memset(a,b,sizeof(a))
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define per(i,j,k) for(int i=(j);i>=(k);--i)
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5, M=2e5+5;
int T, n, m, q, a[M];
int t, block, pos[M], L[450], R[450], tag[450];
uint v[N], w[N], d[450][N];
struct edge {
	int x, y;
} e[M];
mt19937 rd(time(0));
void modify(int l,int r) {
	int p=pos[l], q=pos[r];
	if(p==q) {
		rep(i,l,r) {
			int x=e[i].x, y=e[i].y;
			v[x]^=w[y], v[y]^=w[x];
		}
		return;
	}
	rep(i,p+1,q-1) tag[i]^=1;
	rep(i,l,R[p]) {
		int x=e[i].x, y=e[i].y;
		v[x]^=w[y], v[y]^=w[x];
	}
	rep(i,L[q],r) {
		int x=e[i].x, y=e[i].y;
		v[x]^=w[y], v[y]^=w[x];
	}
}
void solve() {
	n=read(), m=read();
	block=sqrt(m);
	t=m/block;
	rep(i,1,t) L[i]=R[i-1]+1, R[i]=i*block;
	if(R[t]<m) ++t, L[t]=R[t-1]+1, R[t]=m;
	rep(i,1,t) {
		tag[i]=0;
		rep(j,1,n) d[i][j]=0;
	}
	rep(i,1,n) w[i]=rd(), v[i]=0;
	rep(i,1,m) {
		e[i].x=read(), e[i].y=read();
		int x=e[i].x, y=e[i].y;
		v[x]^=w[y];
		v[y]^=w[x];
		pos[i]=(i-1)/block+1;
		d[pos[i]][x]^=w[y];
		d[pos[i]][y]^=w[x];
	} 
	q=read();
	while(q--) {
		int op=read(), l=read(), r=read();
		if(op==1) modify(l,r);
		else {
			int vx=v[l], vy=v[r];
			rep(i,1,t) {
				if(tag[i]) vx^=d[i][l], vy^=d[i][r];
			}
			printf(vx==vy? "1":"0");
		}
	}
	puts("");
}
signed main() {
	T=read();
	while(T--) solve();
}