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

首先发出题目链接： 链接：https://ac.nowcoder.com/acm/contest/883/A 来源：牛客网 涉及：分块，离线算法

点击这里回到2019牛客暑期多校训练营解题—目录贴

---

题目如下 先说一下题目意思：给你一个无向图，图中有$n$个顶点和$m$条边，每个顶点和每条边都有一个编号。 $S(x)$表示与点$x$直接相连的所有点的集合。然后有$q$条两种类型的命令：

1.改变某一个编号区间内的边的状态，即对于区间内每一条边，当这条边存在的时候就删除它，删除后就不存在；当这条边不存在的时候就加上它，加上它就存在了。

2.判断与点$u$和点$v$由且只由一条边相连的所有点是否相等（即判断$S(u)$与$S(v)$是否相同）。

---

我们需要定量的来表示$S(x)$。可以给每一个点一个独有的hash值来表示此点。那么$S(x)$可以定量为与点x直连的点集内所有点的hash值的异或和。

一共n个点，给每一个点一个hash值，可以用随机值来定义：

void random_point() { for(int i = 1; i <= n; i++){ Hash[i] = rand();//Hash[i]表示第i个点的hash值。 } return; }

创建一个数组sign，sign[i]表示当前部分边翻转对于点i的贡献，为什么是部分边，后面再解释。 开始的时候所有边都是存在的，我们要对sign(x)进行初始化

for(int i = 1; i <= m; i++) { scanf("%d%d",&edge[i].point1,&edge[i].point2);//边结构体 sign[edge[i].point1] ^= Hash[edge[i].point2]; sign[edge[i].point2] ^= Hash[edge[i].point1]; } struct Edge{ int point1; int point2; };

---

由于每次翻转的都是一个区间内的所有边，为了减少复杂度，可以对所有的边进行分块处理，一共有m条边，我们可以分成$(int)sqrt(m)$块。除最后一块以外，其他块中的边的数量相同。

由于每一块中，每条边所连的两个点各不相同，可以用一个二维数组$block$来表示每一块对于块内所连点的贡献（$block[i][j]$表示第$i$块对点$j$的贡献），初始化为0，比如说：

当第$cnt$块内有一条边连接了点$u$和点$v$， 那么 $block[cnt][u]\wedge =Hash[v]$ 且 $block[cnt][v]\wedge =Hash[u]$

由于一开始所有的边都是存在的，我们首先对$block$数组进行初始化，同时用一个变量$cnt$来表示真正一共分了多少块。

int blocknum = sqrt(m), cnt = 0;//blocknum表示每一块含有多少边，cnt记录一共分了多少块 for(int i = 1; i <= m; i += blocknum) { cnt++;//增加一个块 flag[cnt] = false; //清空标记 l[cnt] = i;//这一块所含边的序号的左边界 r[cnt] = min(i + blocknum - 1, m);//这一块所含边的序号的右边界，同时要对最后一块进行特殊处理。 for(int j = 1; j <= n; j++) block[cnt][j] = 0;//先把初始化block数组 for(int j = l[cnt]; j <= r[cnt]; j++) {//后面再根据实际的边来初始化block数组 block[cnt][edge[j].point1] ^= Hash[edge[j].point2]; block[cnt][edge[j].point2] ^= Hash[edge[j].point1]; } }

---

于是每次翻转区间内的边：

1.如果某一个块内的边全部都被翻转，我们就给这个块打标记。如果这个块在后面又被翻转了一次，那就删除标记，可以异或来体现标记的添加与删除。

2.如果某一个块内只有一部分的边被翻转，那么就直接暴力求解：对于这一部分边，根据边连接的两个点，对sign数组单独进行更新（假设$v$与$u$相连，如果这条边被删除了，那么sign数组需要再次异或Hash[v]或者Hash[u]来达到点集内删除点的效果）。

if(opt==1) {//翻转的边的序号为x到y int cnt1 = (x - 1) / blocknum + 1;//确定边x在哪一块内 int cnt2 = (y - 1) / blocknum + 1;//确定边y在哪一块内 if(cnt1 + 1 <= cnt2) {//如果边x与边y不在同一块 for(int i = cnt1 + 1; i < cnt2; i++) {//把全部边都翻转的块加上或者减去标记 //flag刚开始为0表示没有被翻转过，如果第一次被反转则异或1相当于打上标记 //如果后面又被全部翻转了一次，相当于还原，异或1则相当于删除表示。 flag[i] ^= 1;//flag即为标记 } //对于两端只有部分边被翻转的块进行暴力操作 for(int i = x; i <= r[cnt1]; i++) { sign[edge[i].point1] ^= Hash[edge[i].point2];//进行异或表示添加或删除 sign[edge[i].point2] ^= Hash[edge[i].point1]; } for(int i = l[cnt2]; i <= y; i++) { sign[edge[i].point2] ^= Hash[edge[i].point1]; sign[edge[i].point1] ^= Hash[edge[i].point2]; } }

---

然后是关于询问的处理 由于在翻转边的时候，真正进行更新的是sign数组，其他的只是对一些块只打了标记，而没有处理，所以可以在询问的时候进行离线处理。

如果访问某两个点$u$和$v$的点集是否相同，我们创建两个两个临时变量$hash1$和$hash2$，分别赋值为当前的$sign[u]$和$sign[v]$。然后遍历每一个块，如果这个块的标记为1表示这个块被翻转过，于是需要异或上这个块对于点u或者点v的贡献，异或既可表示删除贡献也可表示加上贡献（block数组）。

即对于一个点点v，关于这个点真正的点集$S(v)$为： $$S(v)=\underset{flag[i]=1}{{\oplus }_{i=1}^{cnt}}block[i][v]\oplus sign[v]$$

//下面是离线处理 int hash1 = sign[x], hash2 = sign[y];//用两个临时变量储存sign for(int i = 1; i <= cnt; i++) {//遍历每一个块 if(flag[i]) {//如果这个块被打了标记 hash1 ^= block[i][x];//需要异或上这个块对于点x的贡献 hash2 ^= block[i][y];//需要异或上这个块对于点y的贡献 } } printf("%d", (hash1 == hash2));//判断两个点的点集是否相同

由于sign[i]只储存了部分边翻转后对于点i的贡献，另外有些贡献只对块打了标记。但有了离线处理，就不需要考虑被打标记块中每一条边所连接的每一组点，只需考虑当前所给的$u$和$v$点即可。

---

代码如下：

#include <iostream> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; const int msm = 460;//表示sqrt(m)的最大值，用来判断分块的数量 const int maxm = 2e5; const int maxn = 1e5+5; int t, n, m, q;//题目所给变量 int opt, x, y;//每一条指令的三个参数 struct Edge{//边结构体 int point1; int point2; }; ull block[msm][maxn]; //block[i][j]表示第i块对点j的贡献 ull sign[maxn]; //sign[i]表示第i的点所连点的部分集合 bool flag[msm]; //flag[i]表示第i块的标记 ull Hash[maxn]; //Hash[i]表示第i个点的hash值 Edge edge[maxm]; //edge[i]表示第i条边 int l[msm], r[msm]; //l[i]与r[i]分别表示第i块的左边界和右边界 void random_point() { for(int i = 1; i <= n; i++){ Hash[i] = rand();//Hash[i]表示第i个点的hash值。 } return; } int main() { scanf("%d", &t); while(t--) { scanf("%d%d", &n, &m); random_point();//给每一个点一个hash值 for(int i = 1; i <= n; i++) sign[i] = 0;//初始化sign数组 for(int i = 1; i <= m; i++) { scanf("%d%d",&edge[i].point1,&edge[i].point2); //一开始此边存在，所以更新sign数组 sign[edge[i].point1] ^= Hash[edge[i].point2]; sign[edge[i].point2] ^= Hash[edge[i].point1]; } int blocknum = sqrt(m), cnt = 0;//blocknum表示每一块所含的边的个数，cnt表示一共分了多少块 for(int i = 1; i <= m; i += blocknum) { cnt++;//块数加一 flag[cnt] = false;//清空标记 l[cnt] = i;//更新当前块的左边界 r[cnt] = min(i + blocknum - 1, m);//更新当前块的右边界，注意考虑最后一块的特殊性 for(int j = 1; j <= n; j++) block[cnt][j] = 0;//先把初始化block数组 for(int j = l[cnt]; j <= r[cnt]; j++) {//后面再根据实际的边来初始化block数组 block[cnt][edge[j].point1] ^= Hash[edge[j].point2]; block[cnt][edge[j].point2] ^= Hash[edge[j].point1]; } } scanf("%d", &q); while(q--) { scanf("%d%d%d", &opt, &x, &y); if(opt==1) {//命令类型为1，翻转的边的序号为x到y int cnt1 = (x - 1) / blocknum + 1;//确定边x在哪一块内 int cnt2 = (y - 1) / blocknum + 1;//确定边y在哪一块内 if(cnt1 + 1 <= cnt2) {//如果边x与边y不在同一块 for(int i = cnt1 + 1; i < cnt2; i++) {//把全部边都翻转的块加上或者减去标记 //flag刚开始为0表示没有被翻转过，如果第一次被反转则异或1相当于打上标记 //如果后面又被全部翻转了一次，相当于还原，异或1则相当于删除表示。 flag[i] ^= 1;//flag即为标记 } for(int i = x; i <= r[cnt1]; i++) { sign[edge[i].point1] ^= Hash[edge[i].point2];//进行异或表示添加或删除 sign[edge[i].point2] ^= Hash[edge[i].point1]; } for(int i = l[cnt2]; i <= y; i++) { sign[edge[i].point2] ^= Hash[edge[i].point1]; sign[edge[i].point1] ^= Hash[edge[i].point2]; } } else{//如果区间包含于某一个块 for(int i = x; i <= y; i++) {//直接对区间内的边进行更新 sign[edge[i].point2] ^= Hash[edge[i].point1]; sign[edge[i].point1] ^= Hash[edge[i].point2]; } } } else {//命令类型为2 int hash1 = sign[x], hash2 = sign[y];//用两个临时变量储存sign for(int i = 1; i <= cnt; i++) {//遍历每一个块 if(flag[i]) {//如果这个块被打了标记 hash1 ^= block[i][x];//需要异或上这个块对于点x的贡献 hash2 ^= block[i][y];//需要异或上这个块对于点y的贡献 } } printf("%d", (hash1 == hash2));//判断两个点的点集是否相同 } } puts("");//最后输出此字符串的'\0' } return 0; }