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;
}