地址 https://www.acwing.com/problem/content/241/
小A和小B在玩一个游戏。
首先，小A写了一个由0和1组成的序列S，长度为N。
然后，小B向小A提出了M个问题。
在每个问题中，小B指定两个数 l 和 r，小A回答 S[l~r] 中有奇数个1还是偶数个1。
机智的小B发现小A有可能在撒谎。
例如，小A曾经回答过 S[1~3] 中有奇数个1， S[4~6] 中有偶数个1，现在又回答 S[1~6] 中有偶数个1，显然这是自相矛盾的。
请你帮助小B检查这M个答案，并指出在至少多少个回答之后可以确定小A一定在撒谎。
即求出一个最小的k，使得01序列S满足第1~k个回答，但不满足第1~k+1个回答。
输入格式
第一行包含一个整数N，表示01序列长度。
第二行包含一个整数M，表示问题数量。
接下来M行，每行包含一组问答：两个整数l和r，以及回答“even”或“odd”，用以描述S[l~r] 中有奇数个1还是偶数个1。
输出格式
输出一个整数k，表示01序列满足第1~k个回答，但不满足第1~k+1个回答，如果01序列满足所有回答，则输出问题总数量。
数据范围 N≤10^9,M≤10000 输入样例： 10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd 输出样例： 3
解答1：
带权并查集
本题目有两个难点
1 数据范围过大 有 10^9
2 询问的内容如何转化到并查集
问题1 的解决办法是 使用离散化 将不同的数据映射到1 2 3 4。。。，由于只有10000次 询问，每次询问提供两个数据 所以只要提供10000*2的数据范围即可
问题2 的解决办法是 前缀和 如果提供 l和r的范围内1有奇数个还是偶数个 也就是计算 前缀和 sum[r] - sum[l-1]
另由于有偶数减偶数 奇数减奇数 都是偶数 只有两者不同类型分别是奇数偶数中的一种 才会出现最后的差是奇数
那么并查集其实也就是前缀和中每个元素的奇偶性
增加带权数组 所有的前缀和元素都会合并到一个祖先中，d[x]带权数组会记录x元素是否与根是同样的奇偶性
当得到新的询问时候 如果两个元素已经合并在同一个祖先下，那么就可以根据他们与祖先的异同得到他们的异同，再来判断他们与输入的异同是否一致 如果不一致就是发生矛盾，返回即可
代码如下
1 #include <iostream> 2 #include <string> 3 #include <unordered_map> 4 5 using namespace std; 6 7 const int MAX_M = 20010; 8 9 int N, M; 10 int n, m; 11 12 int fa[MAX_M]; 13 int d[MAX_M]; 14 15 int idx = 0; 16 17 unordered_map<int, int> S; 18 19 20 //离散化 21 int get(int x) { 22 if (S.count(x) == 0) S[x] = ++idx; 23 return S[x]; 24 } 25 26 void init() 27 { 28 for (int i = 0; i < MAX_M; i++) { 29 fa[i] = i; 30 } 31 } 32 33 int find(int x) { 34 if (fa[x] != x) { 35 int root = find(fa[x]); 36 d[x] += d[fa[x]]%2; 37 fa[x] = root; 38 } 39 40 return fa[x]; 41 } 42 43 44 int main() 45 { 46 47 cin >> n >> m; 48 int res = m; 49 init(); 50 for (int i = 1; i <= m; i++) { 51 int a, b; string s; 52 cin >> a >> b >> s; 53 a = get(a - 1); b = get(b); 54 int pa = find(a), pb = find(b); 55 56 if (pa == pb) { 57 //查看两者是否符合之前的信息 58 if (s == "even") 59 { 60 //两者奇偶性相同 61 if( (d[a] + d[b]) % 2 != 0){ 62 //有矛盾 63 res = i - 1; 64 break; 65 } 66 } 67 else if (s == "odd") { 68 //两者奇偶性不同 69 if ((d[a] + d[b]) % 2 != 1) { 70 //有矛盾 71 res = i - 1; 72 break; 73 } 74 } 75 else { 76 cout << s << endl; 77 cout << "error" << endl; 78 break; 79 } 80 } 81 else { 82 //pa != pb 83 //合并 84 fa[pa] = pb; 85 int add = 0; 86 if (s == "odd") add = 1; 87 d[pa] = (d[a] + d[b] + add)%2; 88 } 89 90 91 } 92 cout << res << endl; 93 94 95 96 return 0; 97 }