AcWing 239. 奇偶游戏（带权并查集，扩展域并查集）

本文主要是介绍AcWing 239. 奇偶游戏（带权并查集，扩展域并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小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≤109,M≤10000
输入样例：
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
输出样例：
3

边带权并查集好像忘得差不多了，赶紧复习一下

思路：
如果区间 $[l, r]$ 为奇数，代表 $s u m [l - 1]$ 和 $s u m [r]$ 的奇偶性不同，否则奇偶性相同。我们以此建立关系。

定义 $d [i]$ 代表 $i$ 与根节点的奇偶关系，如果为1代表奇偶性不同，否则奇偶性相同。关系传递直接通过关系相加再模2（因为相同奇偶性加上不改变，不同奇偶性加上改变）。

#include <ctime>
#include <iostream>
#include <assert.h>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <map>using namespace std;
const int maxn = 2e5 + 7;
const int mod = 10007;int b[maxn],cnt;
int fa[maxn],d[maxn];
int n,m;struct Query {int l,r;int kind; //1代表奇数，0代表偶数
}q[maxn];int Find(int x) {return lower_bound(b + 1,b + 1 + cnt,x) - b;
}void Input() {scanf("%d%d",&n,&m);for(int i = 1;i <= m;i++) {char op[10];scanf("%d%d%s",&q[i].l,&q[i].r,op);if(op[0] == 'o') q[i].kind = 1;else q[i].kind = 0;b[++cnt] = q[i].l - 1;b[++cnt] = q[i].r;}sort(b + 1,b + 1 + cnt);cnt = unique(b + 1,b + 1 + cnt) - (b + 1);
}int findset(int x) {if(x == fa[x]) return x;int rt = findset(fa[x]);d[x] = (d[x] + d[fa[x]]) % 2;return fa[x] = rt;
}void Solve() {for(int i = 1;i <= cnt;i++) {fa[i] = i;}for(int i = 1;i <= m;i++) {int x = Find(q[i].l - 1),y = Find(q[i].r);int rx = findset(x),ry = findset(y);if(rx != ry) {fa[rx] = ry;d[rx] = (d[x] + d[y] + q[i].kind) % 2;} else {if((d[x] + d[y]) % 2 != q[i].kind) {printf("%d\n",i - 1);return ;}}}printf("%d\n",m);
}int main() {Input();Solve();return 0;
}

扩展域并查集：
定义x域为偶数域（或者是奇偶性相同），x+n域为奇数域（或者是奇偶性不同）
那么相同奇偶性的两个集和，奇偶性相同，所以偶数域和奇数域分别合并。
奇偶性不同的两个集和，就是偶数域合并另一个数的奇数域，奇数域合并另一个数的偶数域。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;const int maxn = 3e5 + 7;int fa[maxn];
int n,m,cnt;
int b[maxn];struct Query {int l,r;int kind;
}q[maxn];int Find(int x) {return lower_bound(b + 1,b + 1 + cnt,x) - b;
}int findset(int x) {if(x == fa[x]) return x;return fa[x] = findset(fa[x]);
}void Union(int x,int y) {int rx = findset(x),ry = findset(y);if(rx != ry) fa[rx] = ry;
}void Input() {scanf("%d%d",&n,&m);for(int i = 1;i <= m;i++) {char op[10];scanf("%d%d%s",&q[i].l,&q[i].r,op);b[++cnt] = q[i].l - 1;b[++cnt] = q[i].r;if(op[0] == 'o') q[i].kind = 1;else q[i].kind = 0;}sort(b + 1,b + 1 + cnt);cnt = unique(b + 1,b + 1 + cnt) - (b + 1);
}void Solve() {for(int i = 1;i <= 2 * cnt;i++) fa[i] = i;for(int i = 1;i <= m;i++) {int x = Find(q[i].l - 1),y = Find(q[i].r);if(q[i].kind == 0) {if(findset(x) == findset(y + cnt)) {printf("%d\n",i - 1);return;}Union(x,y);Union(x + cnt,y + cnt);}else {if(findset(x) == findset(y)) {printf("%d\n",i - 1);return;}Union(x,y + cnt);Union(x + cnt,y);}}printf("%d\n",m);
}int main() {Input();Solve();return 0;
}