奇偶游戏（边带权）

AcWing-239-奇偶游戏

分析

见《进阶指南》第197页。

实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10010;
struct node {
    int l, r, ans;
};
int n, m;
node a[N];
int cnt, nums[2 * N];
int f[2 * N], d[2 * N];

void discrete () {
    for (int i = 1; i <= m; ++ i) {
        nums[++ cnt] = a[i].l - 1;
        nums[++ cnt] = a[i].r;
    }
    sort(nums + 1, nums + cnt + 1);
    n = unique(nums + 1, nums + cnt + 1) - (nums + 1);
}
int query (int x) {
    return lower_bound(nums + 1, nums + n + 1, x) - nums;
}
int find (int x) {
    if (f[x] == x) return x;

    int rt = find(f[x]);
    d[x] ^= d[f[x]];
    return f[x] = rt;
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++ i) {
        char str[10];
        scanf("%d%d%s", &a[i].l, &a[i].r, str);
        a[i].ans = (str[0] == 'o' ? 1 : 0);
    }

    discrete();
    for (int i = 1; i <= n; ++ i) f[i] = i;
    for (int i = 1; i <= m; ++ i) {
        int x = query(a[i].l - 1), y = query(a[i].r);
        int fx = find(x), fy = find(y);
        if (fx == fy) {
            if((d[x] ^ d[y]) != a[i].ans) {
                printf("%d", i - 1);
                return 0;
            }
        } else {
            d[fy] = d[x] ^ d[y] ^ a[i].ans;
            f[fy] = fx;
        }
    }
    printf("%d", m);
    return 0;
}