题目链接：https://ac.nowcoder.com/acm/contest/883/A
题目大意：
给出一个无向图和m条边，处理Q个询问
对于1 x y，将边序号为x到y的边反转，如果存在这条边则删除，不存在则增加。
对于2 x y，回答与点x直接相连的点集是否与y直接相连的点集是否相同，是则输出1，不是输出0
解题报告：
将m条边分块，可以预处理出每个块内 点的异或和，如果1操作是对这整个块进行删除，则打上标记即可，遍历的时候只需异或上这段区间的异或和。
对于块内操作，直接块内暴力即可。
真的是神仙题解...
AC代码：
1 #include<bits/stdc++.h> 2 #define numm ch-48 3 #define pd putchar(' ') 4 #define pn putchar(' ') 5 #define pb push_back 6 #define fi first 7 #define se second 8 #define fre1 freopen("1.txt","r",stdin) 9 #define fre2 freopen("2.txt","w",stdout) 10 #define debug cout<<"debug"<<endl 11 using namespace std; 12 template <typename T> 13 void read(T &res) { 14 bool flag=false;char ch; 15 while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true); 16 for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm); 17 flag&&(res=-res); 18 } 19 template <typename T> 20 void write(T x) { 21 if(x<0) putchar('-'),x=-x; 22 if(x>9) write(x/10); 23 putchar(x%10+'0'); 24 } 25 typedef long long ll; 26 const int maxn=200005; 27 const int maxm=505; 28 const int mod=1e9+7; 29 ll has[maxn]; ///每个点的权值 30 ll a[maxn],b[maxn]; 31 int block[maxn];///每个点对应的块 32 int lef[maxm]; ///每个块的左边界 33 int rig[maxm]; ///每个块的右边界 34 int flag[maxm]; ///每个块内的边是否被反转的标记 35 ll mp[maxm][maxn];///每个块连的点的权值 36 ll val[maxn]; ///当前的权值,用于判断 37 int main() 38 { 39 srand(unsigned(time(NULL))); 40 for(int i=1;i<=maxn-5;i++) ///每个点都有自己的权值 41 has[i]=rand(); 42 int t,q,n,m; 43 read(t); 44 while(t--) { 45 read(n),read(m); 46 int bl=sqrt(m); 47 for(int i=1;i<=n;i++) 48 val[i]=0; 49 for(int i=1;i<=m;i++) 50 block[i]=(i-1+bl)/bl; 51 for(int i=1;i<=(m-1+bl)/bl;i++) { 52 lef[i]=(i-1)*bl+1; 53 rig[i]=min(i*bl,m); 54 flag[i]=0; 55 for(int j=1;j<=n;j++) 56 mp[i][j]=0; 57 } 58 for(int i=1;i<=m;i++) { 59 read(a[i]),read(b[i]); 60 mp[block[i]][a[i]]^=has[b[i]]; 61 mp[block[i]][b[i]]^=has[a[i]]; 62 } 63 read(q); 64 string ans=""; 65 while(q--) { 66 int op,x,y; 67 read(op),read(x),read(y); 68 if(op==2) { 69 ll sa=val[x],sb=val[y]; 70 for(int i=1;i<=(m-1+bl)/bl;i++) 71 if(!flag[i]) { 72 sa^=mp[i][x]; 73 sb^=mp[i][y]; 74 } 75 ans+=((sa==sb)?"1":"0"); 76 }else { 77 if(block[x]+1<block[y]) { 78 for(int i=x;i<=rig[block[x]];i++) 79 val[a[i]]^=has[b[i]],val[b[i]]^=has[a[i]]; 80 for(int i=block[x]+1;i<block[y];i++) 81 flag[i]^=1; 82 for(int i=lef[block[y]];i<=y;i++) 83 val[a[i]]^=has[b[i]],val[b[i]]^=has[a[i]]; 84 } 85 else { 86 for(int i=x;i<=y;i++) 87 val[a[i]]^=has[b[i]],val[b[i]]^=has[a[i]]; 88 } 89 } 90 } 91 cout<<ans<<endl; 92 } 93 return 0; 94 }