小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≤10000N≤109,M≤10000
输入样例：
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
输出样例：
3带权并查集：
题解：如果我们用sum数组表示序列S的前缀和，那么在每个回答中：
1、S[l ~ r] 有偶数个1，等价于 sum[l - 1] 与 sum[r] 奇偶性相同。
2、S[l ~ r] 有奇数个1，等价于 sum[l - 1] 与 sum[r] 奇偶性不同。
注意，我们在本题中不需要求sum数组，只要把它看成一个变量。
1、x 与 x 的奇偶性相同，x 与 x 的奇偶性也相同，那么 x 与 x 的奇偶性相同。
2、x 与 x 的奇偶性相同，x 与 x 的奇偶性不同，那么 x 与 x 的奇偶性不同。
3、x 与 x 的奇偶性不同，x 与 x 的奇偶性不同，那么 x 与 x 的奇偶性相同。
假设 d[x] 是 x ~ p 的奇偶性， d[y] 是 y ~ q 的奇偶性， d[p] 是 p ~ q 是奇偶性（其中x ~ p 和 y ~ q是两个不同的集合，p ~ q是两个集合的路径）。那么，ans = d[x] ^ d[y] ^ d[p]，可以推出d[p] = d[x] ^ d[y] ^ ans（读者可以自己证明）。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector> using namespace std; const int maxn = 1e4+; struct node {
int l, r, ans;
}arr[maxn]; vector<int> v;
int f[maxn];
int d[maxn];
int n, m; int find(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + ;
} void init() {
v.clear();
for(int i = ; i <= m; i++) {
char str[];
scanf("%d %d %s", &arr[i].l, &arr[i].r, str);
arr[i].ans = (str[] == 'o') ? : ; //奇数为1，偶数为0
v.push_back(arr[i].l - );
v.push_back(arr[i].r);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end()); //离散化
n = v.size();
for(int i = ; i <= n; i++) {
f[i] = i;
d[i] = ;
}
} int get(int x) {
if(x == f[x]) {
return f[x];
}
int root = get(f[x]);
d[x] ^= d[f[x]];
return f[x] = root;
} int main() {
scanf("%d %d", &n, &m);
init();
for(int i = ; i <= m; i++) {
int x = find(arr[i].l - );
int y = find(arr[i].r);
int fx = get(x);
int fy = get(y);
if(fx == fy) {
if((d[x] ^ d[y]) != arr[i].ans) { //与前面的回答相矛盾
printf("%d\n", i - );
return ;
}
} else {
f[fx] = fy;
d[fx] = d[x] ^ d[y] ^ arr[i].ans;
}
}
printf("%d\n", m);
return ;
}
扩展域并查集：
题解：同上，如果我们用sum数组表示序列S的前缀和，那么在每个回答中：
1、S[l ~ r] 有偶数个1，等价于 sum[l - 1] 与 sum[r] 奇偶性相同。
2、S[l ~ r] 有奇数个1，等价于 sum[l - 1] 与 sum[r] 奇偶性不同。
注意，我们在本题中不需要求sum数组，只要把它看成一个变量。
我们可以把变量x拆成两个节点x和xeven，其中x表示sum[x]是奇数，x表示sum[x]是偶数。我们那也可以把这两个节点称为x的“奇数域”和“偶数域”。
对于每个问题，设在离散化后l - 1和r的值分别是x和y，设ans表示该问题回答（0表示偶数个1，1表示奇数个1）
1、若ans = 0是，则合并x与y，x和y。这表示“x为奇数”和“y为奇数”可以互相推出，“x位偶数”和“y位偶数”可以互相推出。
2、若ans = 0是，则合并x与y，x和y。这表示“x为奇数”和“y为偶数”可以互相推出，“x位偶数”和“y位奇数”可以互相推出。
上述合并还维护了关系的传递性。若x和y在同一集合内，则两者的奇偶性相同。若x和y在同一集合内，则两者的奇偶性不同。
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm> using namespace std; const int maxn = 1e4+; struct node {
int l, r, ans;
}arr[maxn]; vector<int> v;
int f[maxn];
int n, m; void init() {
for(int i = ; i <= m; i++) {
char str[];
scanf("%d %d %s", &arr[i].l, &arr[i].r, str);
arr[i].ans = (str[] == 'o') ? : ; //奇数为1，偶数为0
v.push_back(arr[i].l - );
v.push_back(arr[i].r);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
n = v.size();
for(int i = ; i <= * n; i++) {
f[i] = i;
}
} int find(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + ;
} int get(int x) {
if(x == f[x]) {
return f[x];
}
int root = get(f[x]);
return f[x] = root;
} int main() {
scanf("%d %d", &n, &m);
init();
for(int i = ; i <= m; i++) {
int x = find(arr[i].l - );
int y = find(arr[i].r);
int x_odd = x, x_even = x + n;
int y_odd = y, y_even = y + n;
if(arr[i].ans == ) { //回答奇偶性相同
if(get(x_odd) == get(y_even)) { //与已知情况矛盾
printf("%d\n", i - );
return ;
}
f[get(x_odd)] = get(y_odd);
f[get(x_even)] = get(y_even);
} else { //回答奇偶性不同
if(get(x_odd) == get(y_odd)) { //与已知情况矛盾
printf("%d\n", i - );
return ;
}
f[get(x_odd)] = get(y_even);
f[get(x_even)] = get(y_odd);
}
}
printf("%d\n", m); //没有说谎
return ;
}