我们用sum数组来表示序列S的前缀和，那么在每次的回答中：
1 S[l~r]有偶数个1，等价于sum[l-1]与sum[r]的奇偶性相同。
2 S[l~r]有偶数个1，等价于sum[l-1]与sum[r]的奇偶性不同。
我们有如下传递关系：
1.若x1与x2奇偶性相同，x2与x3奇偶性也相同，那么x1与x3的奇偶性也相同。
2. 若x1与x2奇偶性相同，x2与x3奇偶性不同，那么x1与x3的奇偶性不同。
3.2. 若x1与x2奇偶性不同，x2与x3奇偶性不同，那么x1与x3的奇偶性相同。
另外本体序列长度N很大，但M较小，可以先对数据离散化，
第一种 边带权并查集
上面的传递关系和异或操作很相似，我们考虑一下异或操作。
边权d[x]为0，表示x与fa[x]的奇偶性相同，d[x]为1，表示不同，我们在路径压缩时，对x到树根路径上的所有边权做异或运算，即可得到x与树根的奇偶关系。
设l-1与r离散化后得到的值为x,y。
若x,y在一个集合，d[x]^d[y]既x和y的奇偶关系。若d[x]^d[y]!=ans,则在撒谎。
若x,y不在一个集合，则合并两个集合，同时更新新边的边权d[p]=d[x]^d[y]^ans.
//边带权并查集 #include<bits/stdc++.h> using namespace std; const int N = 2e4 + 10; int fa[N], a[N], tot,n,m,d[N]; struct node{ int l, r, ans; }b[N]; void read()//读入 离散化 { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { char s[6]; scanf("%d%d%s", &b[i].l, &b[i].r, s); b[i].ans = (s[0] == ‘o‘ ? 1 : 0);//奇数个s[l-1]与s[r]奇偶性不相同，偶数个相同 a[++tot] = b[i].l - 1; a[++tot] = b[i].r; } sort(a + 1, a + tot + 1); tot = unique(a + 1, a + tot + 1) - a - 1; } int get(int x) { if (x == fa[x]) return x; int root = get(fa[x]); d[x] ^= d[fa[x]]; return fa[x] = root; } int main() { read(); for (int i = 0; i <= tot; i++) fa[i] = i; int x, y; for (int i = 1; i <= m; i++) { //求出l-1和r离散化后的值 x = lower_bound(a + 1, a + tot + 1, b[i].l - 1) - a; y = lower_bound(a + 1, a + tot + 1, b[i].r) - a; //执行get函数，得到树根，并进行路径压缩 int p = get(x), q = get(y); if (p == q)//已在同一集合 { if (d[x] ^ d[y] != b[i].ans)//不满足 { cout << i - 1 << endl; return 0; } } else//不在同一集合，合并 { fa[p] = q; d[p] = d[x] ^ d[y] ^ b[i].ans; } } cout << m << endl; return 0; }
第二种 扩展域并查集
把每个点x拆成两个节点x_odd,x_even,x_odd表示sum[x]为奇数，x_even表示偶数，这两个节点分别是x的奇数域和偶数域
#include<bits/stdc++.h> using namespace std; const int N = 2e4 + 10; int fa[2*N], a[N], tot,n,m; struct node{ int l, r, ans; }b[N]; int get(int x) { if (x == fa[x]) return x; return fa[x] = get(fa[x]); } void read() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { char s[6]; scanf("%d%d%s", &b[i].l, &b[i].r, s); b[i].ans = (s[0] == ‘o‘ ? 1 : 0); a[++tot] = b[i].l - 1; a[++tot] = b[i].r; } sort(a + 1, a + tot + 1); tot = unique(a + 1, a + tot + 1) - a - 1; } int main() { read(); for (int i = 0; i <= 2*tot; i++) fa[i] = i; int x, y; for (int i = 1; i <= m; i++) { x = lower_bound(a + 1, a + tot + 1, b[i].l - 1) - a; y = lower_bound(a + 1, a + tot + 1, b[i].r) - a; int x_odd = x, x_even = x + tot; int y_odd = y, y_even = y + tot; if (b[i].ans) { if (get(x_odd)==get(y_odd)) { cout << i - 1 << endl; return 0; } fa[get(x_odd)] = get(y_even); fa[get(x_even)] = get(y_odd); } else { if (get(x_odd) == get(y_even)) { cout << i - 1 << endl; return 0; } fa[get(x_odd)] = get(y_odd); fa[get(x_even)] = get(y_even); } } cout << m << endl; return 0; }
原文：https://www.cnblogs.com/xiaoguapi/p/10447515.html
