传送门
题意：有一个长度已知的01串，给出[l,r]这个区间中的1是奇数个还是偶数个，给出一系列语句问前几个是正确的
思路：如果我们知道[1,2][3,4][5,6]区间的信息，我们可以求出[1,6]的信息
可以将将闭区间[x,y]转换成(x 1,y]左开右闭区间
那么我们可以用并查集来做，每次输入两个数 x 和 y 判断两者是否在同一并查集中，如果在，那么可以直接判断奇偶
如果两者不在同一并查集中将两者合并，并求出两者的根之间的距离
距离可在 find 函数中维护
注意：数据范围比较大，需要离散化
——代码
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #define N 1000001 5 6 int n, m, cnt, ans; 7 int a[N], b[N], q[N << 1], f[N << 1], d[N << 1]; 8 char s[N][10]; 9 10 inline int read() 11 18 19 inline int find(int x) 20 27 return f[x]; 28 } 29 30 int main() 31 45 std::sort(q + 1, q + cnt + 1); 46 cnt = std::unique(q + 1, q + cnt + 1) q 1; 47 for(i = 1; i <= cnt; i++) f[i] = i, d[i] = 0; 48 for(i = 1; i <= m; i++) 49 58 else 59 ans++; 64 } 65 printf("%d\n", ans); 66 } 67 return 0; 68 }View Code
上一篇：[CODEVS1912] 汽车加油行驶问题（分层图最短路）
下一篇：[luoguP1993] 小 K 的农场（差分约束 + spfa 判断负环）
并查集 离散化
