奇偶游戏（扩展域）

AcWing-239-奇偶游戏

分析

见《进阶指南》第200页。

实现

#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[4 * 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;
    return f[x] = find(f[x]);
}
void merge (int x, int y) {
    f[find(x)] = find(y);
}
bool query (int x, int y) {
    return find(x) == find(y);
}

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 <= 2 * n; ++ i) f[i] = i;
    for (int i = 1; i <= m; ++ i) {
        int x = query(a[i].l - 1), y = query(a[i].r);
        if (a[i].ans == 0) {
            if (query(x, y + n) == true) {
                printf("%d", i - 1);
                return 0;
            }
            merge(x, y);
            merge(x + n, y + n);
        } else {
            if (query(x, y) == true) {
                printf("%d", i - 1);
                return 0;
            }
            merge(x, y + n);
            merge(x + n, y);
        }
    }
    printf("%d", m);
    return 0;
}