2019牛客暑期多校训练营（第三场）A Graph Games（分块）

题目链接：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('\n')
 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 }      

代码在这里！

转载于:https://www.cnblogs.com/wuliking/p/11342103.html