python/TangDou/AcWing_TiGao/T4/239_DaiQuan_Static_ErFen.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 20010;

// 结构体记录原始输入
struct Node {
    int x, y, e;
} g[N];

int n, m;

// 离散化静态数组+二分查找新位置
int b[N], bl;
int get(int x) {
    return lower_bound(b, b + bl, x) - b;
}

// 带边权更新并查集模板
int p[N], d[N];
int find(int x) {
    if (x == p[x]) return x;
    int root = find(p[x]);
    d[x] += d[p[x]];
    return p[x] = root;
}

int main() {
    scanf("%d %d", &n, &m);
    n = 0;                                // 序列的长度没有用处，我们只关心每个a,b范围内的数字1的个数
    for (int i = 1; i < N; i++) p[i] = i; // 初始化并查集

    for (int i = 1; i <= m; i++) {
        int x, y;
        char t[100];
        scanf("%d %d %s", &x, &y, t);

        g[i].x = x, g[i].y = y;
        if (t[0] == 'e')
            g[i].e = 0;
        else
            g[i].e = 1;

        // 记录下来
        b[bl++] = x, b[bl++] = y;
    }

    // 离散化去重
    sort(b, b + 2 * m);
    bl = unique(b, b + 2 * m) - b;

    int res = m;
    for (int i = 1; i <= m; i++) {
        int a = g[i].x, b = g[i].y, e = g[i].e;
        // 类前缀和
        a = get(a - 1), b = get(b);
        int t = 0;         // 偶数个1
        if (e == 1) t = 1; // 奇数个1

        // 并查集
        int pa = find(a), pb = find(b);
        if (pa == pb) {
            if (abs(d[a] - d[b]) % 2 != t) {
                res = i - 1; // 最后一条正确的序号
                break;
            }
        } else {
            p[pa] = pb;
            d[pa] = abs(d[a] - d[b] - t) % 2;
        }
    }
    printf("%d\n", res);
    return 0;
}