Graph Games

牛客多校第三场题目链接给n个点m条边两种操作1是反转l到r之间的边把有边变成无边把无边变成有边。2是询问两个点所在的点集是否相同。对边进行分块我们首先得给每个点随即一个值判断两个点是否在一个集合内直接判断这个点和他相邻的点异或之后的两个值是否相同。首先我们先预处理出每个块中的每个点和他相连点的异或值然后对于1操作对于完整块我们直接用标记数组标记一下反转了偶数次还是奇数次对于不完整的块直接暴力异或这个点相连的点对于操作二 我们将每个块中预处理出来的这个点的值和这个点进行异或如果标记数组是偶数次那么说明之前连着边现在还是连着如果是奇数次那说明这个块中的边都没了那就不用进行异或。#includebits/stdc.husing namespace std;constintN10000010;constintM20000010;intlazy[5005];inta[M],b[M],L[5005],R[5005];intB[5005][N];intO[N];inttot0;inthas[N],pos[M];voidupdate(intl,intr){intxpos[l];intypos[r];if(y-x2){for(intil;ir;i){O[a[i]]^has[b[i]];O[b[i]]^has[a[i]];}return;}for(intil;iR[x];i){O[a[i]]^has[b[i]];O[b[i]]^has[a[i]];}for(intiL[y];ir;i){O[a[i]]^has[b[i]];O[b[i]]^has[a[i]];}for(intix1;iy-1;i){lazy[i]^1;}}intquery(intu,intv){intxO[u],yO[v];for(inti1;itot;i){if(!lazy[i]){x^B[i][u],y^B[i][v];}}returnxy?1:0;}intmain(){srand(time(0));for(inti0;i100000;i){has[i]rand();}intt;scanf(%d,t);while(t--){intn,m;scanf(%d%d,n,m);intblocksqrt(m);for(inti0;in;i)O[i]0;for(inti1;im;i){scanf(%d%d,a[i],b[i]);}tot0;for(inti1;im;iblock){L[tot]i;R[tot]min(m,iblock-1);lazy[tot]0;for(intj1;jn;j)B[tot][j]0;for(intjL[tot];jR[tot];j){B[tot][a[j]]^has[b[j]];B[tot][b[j]]^has[a[j]];}}for(inti1;itot;i){for(intjL[i];jR[i];j){pos[j]i;}}intq;scanf(%d,q);while(q--){intx,l,r;scanf(%d%d%d,x,l,r);if(x1){update(l,r);}else{coutquery(l,r);}}coutendl;}}