acwing 239. 奇偶游戏 并查集

地址 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 }

带权并查集