C++ 代码
//1.如果我们用 sum 数组表示序列 S 的前缀和, 那么在每个回答中:
// 1.S[l ~ r] 有偶数个1, 等价于 sum[l - 1] 与 sum[r] 奇偶性相同(奇 或 偶 + 偶 = 奇 或 偶)
// 2.S[l ~ r] 有奇数个1, 等价于 sum[l - 1] 与 sum[r] 奇偶性不同(奇 或 偶 + 奇 = 偶 或 奇)
// 3.所以我们就可以将这道题给出的俩个数 l 和 r , 转化为 l - 1 和 r 的奇偶性的关系
//2.这道题的序列长度 N 非常大, 而 M 非常小, 需要进行离散化
//3.根据关系的传递性,我们可以用"边带权"的并查集来做
// 边权d[x] = 0,表示x 与 f[x]的奇偶性相同; 为 1,表示 x 与 f[x] 的奇偶性不同,在路径压缩的过程中,对x到树根路径的所有边权做异或(xor)
// 运算,即可得到 x 与树根的奇偶性关系
//4.对于每个问题, 设离散化后 l - 1 和 r 的值分别是 x 和 y , 设ans表示问题的回答(0表示偶数个, 1表示奇数个)
// 若 x 和 y 在一个集合中, 直接判断d[x] ^ d[y] 是否等于ans, 若不等于,则矛盾,直接输出结果
// 若 x 和 y 不在一个集合中,合并俩个集合,得到俩个的树根p 和 q, d[x]与d[y]分别表示 x ~ p 与 y ~ q 之间所有边权的 “xor” 和,
// p ~ q之间的边权为d[p], 显然, 路径x ~ y 由 x ~ p, p ~ q, q ~ y 组成,所以x 与 y 的奇偶性关系ans = d[x] ^ d[y] ^ d[p],
// 得到 d[p] = d[x] ^ d[y] ^ ans
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
const int N = 10010;
int f[N* 2], d[N* 2];
int n, m, t = 1;
struct p{
int x, y, q;
};
p arr[N];
int mp[2 * N];
int Find(int x)
{
if(x == f[x])return x;
int root = Find(f[x]);
d[x] ^= d[f[x]];
return f[x] = root;
}
void read_in()//读入
{
cin >> n >> m;
int a, b;
string c;
for(int i = 1; i <= m; i++){
cin >> a >> b >> c;
mp[++t] = a - 1;
mp[++t] = b;
arr[i].x = a, arr[i].y = b;
if(c[0] == 'e')arr[i].q = 0;
else arr[i].q = 1;
}
sort(mp + 1, mp + t + 1); //排序
n = unique(mp + 1, mp + 1 + t) - mp - 1; //去重, 离散化
}
int main()
{
read_in();
for(int i = 1; i <= n; i++)
f[i] = i;
bool flag = false;
for(int i = 1; i <= m; i++){
//求出l - 1 和 r 离散化后的值
int x = lower_bound(mp + 1, mp + 1 + n, arr[i].x - 1) - mp;
int y = lower_bound(mp + 1, mp + 1 + n, arr[i].y) - mp;
int p = Find(x);
int q = Find(y);
if(p == q){ //如果 p 和 q 在一个集合中
if(d[x] ^ d[y] != arr[i].q){ //矛盾,直接输出
cout << i - 1 << endl;
flag = true;
break;
}
}
else{
f[p] = q;
d[p] = d[x] ^ d[y] ^ arr[i].q;
}
}
if(!flag)cout << m << endl;
return 0;
}