【算法】奇偶游戏（带权并查集）

题目

小 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，表示 0101 序列长度。

第二行包含一个整数 M，表示问题数量。

接下来 M 行，每行包含一组问答：两个整数 l 和 r，以及回答 even 或 odd，用以描述 S[l∼r] 中有偶数个 1 还是奇数个 1。

输出格式

输出一个整数 k，表示 01 序列满足第 1∼k 个回答，但不满足第 1∼k+1 个回答，如果 01 序列满足所有回答，则输出问题总数量。

数据范围

N≤10^9,M≤5000

思路

这道题与银河英雄传说思路是相似的。

我们可以想象为L到R的距离是奇数还是偶数（R为根节点）。

两个集合合并的时候，使得其中一个集合S1的祖先节点排到另一个集合S2的末尾，S1中所有的点到根节点的距离加上S1祖先节点到S2祖先节点的距离%2。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 20010;
int n,m;
int p[N],d[N];
unordered_map<int,int> S;int get(int x)
{if(S.count(x) == 0) S[x] = ++n;return S[x];
}int find(int x)
{if(p[x] != x){int root = find(p[x]);d[x] ^= d[p[x]];p[x] = root;}return p[x];
}int main()
{cin >> n >> m;n = 0;for(int i = 0; i < N; i ++) p[i] = i;int res = m;for(int i = 1; i <= m; i ++){int a,b;string type;cin >> a >> b >> type;a = get(a - 1), b = get(b);int t = 0;if(type == "odd") t = 1;int pa = find(a),pb = find(b);if(pa == pb){if((d[a] ^ d[b] != t)){res = i - 1;break;}}else{p[pa] = pb;d[pa] = d[a] ^ d[b] ^ t;}}cout << res << endl;return 0;
}