Graph Games

牛客多校第三场
题目链接
给n个点m条边
两种操作1是反转l到r之间的边，把有边变成无边，把无边变成有边。
2是询问两个点所在的点集是否相同。

对边进行分块，我们首先得给每个点随即一个值，判断两个点是否在一个集合内，直接判断这个点和他相邻的点异或之后的两个值是否相同。首先我们先预处理出每个块中的每个点和他相连点的异或值，然后对于1操作，对于完整块我们直接用标记数组标记一下反转了偶数次还是奇数次，对于不完整的块直接暴力异或这个点相连的点，对于操作二 我们将每个块中预处理出来的这个点的值和这个点进行异或，如果标记数组是偶数次那么说明之前连着边现在还是连着，如果是奇数次那说明这个块中的边都没了那就不用进行异或。

#include<bits/stdc++.h>using namespace std;constintN=100000+10;constintM=200000+10;intlazy[5005];inta[M],b[M],L[5005],R[5005];intB[5005][N];intO[N];inttot=0;inthas[N],pos[M];voidupdate(intl,intr){intx=pos[l];inty=pos[r];if(y-x<2){for(inti=l;i<=r;i++){O[a[i]]^=has[b[i]];O[b[i]]^=has[a[i]];}return;}for(inti=l;i<=R[x];i++){O[a[i]]^=has[b[i]];O[b[i]]^=has[a[i]];}for(inti=L[y];i<=r;i++){O[a[i]]^=has[b[i]];O[b[i]]^=has[a[i]];}for(inti=x+1;i<=y-1;i++){lazy[i]^=1;}}intquery(intu,intv){intx=O[u],y=O[v];for(inti=1;i<=tot;i++){if(!lazy[i]){x^=B[i][u],y^=B[i][v];}}returnx==y?1:0;}intmain(){srand(time(0));for(inti=0;i<=100000;i++){has[i]=rand();}intt;scanf("%d",&t);while(t--){intn,m;scanf("%d%d",&n,&m);intblock=sqrt(m);for(inti=0;i<=n;i++)O[i]=0;for(inti=1;i<=m;i++){scanf("%d%d",&a[i],&b[i]);}tot=0;for(inti=1;i<=m;i+=block){L[++tot]=i;R[tot]=min(m,i+block-1);lazy[tot]=0;for(intj=1;j<=n;j++)B[tot][j]=0;for(intj=L[tot];j<=R[tot];j++){B[tot][a[j]]^=has[b[j]];B[tot][b[j]]^=has[a[j]];}}for(inti=1;i<=tot;i++){for(intj=L[i];j<=R[i];j++){pos[j]=i;}}intq;scanf("%d",&q);while(q--){intx,l,r;scanf("%d%d%d",&x,&l,&r);if(x==1){update(l,r);}else{cout<<query(l,r);}}cout<<endl;}}