Poj1733 Parity Game（带权并查集）

题面

Poj

题解

反正只要你判断是否满足区间的奇偶性，假设每一位要么是$1$要么是$0$好了。

假设有$S$的前缀和为$sum[]$，则有：

若$S[l…r]$中有奇数个$1$，则$sum[l-1]$与$sum[r]$不同奇偶；反之，则同奇偶

用一个带权并查集维护，设权值数组$s[i]$表示区间$[root[i]…i]$的和的奇偶性。

对于一个区间$[l,r]$，分情况讨论：

如果$root[l]=root[r]$，直接判断就行了。

否则的话，计算一下$s[fv]=t\oplus s[u]\oplus s[v]$

但是$n$太大了，需要离散化（懒人离散化用$map$，美滋滋）

#include <map> 
#include <cstdio>
#include <cstring>
using std::map;
typedef long long ll;

const ll N = 1e4 + 10, Q = 5e3 + 10;
ll n, q, s[N], f[N], cnt;
map <ll, ll> m;

ll find (ll x) {
    if(f[x] == -1) return x;
    ll tmp = find(f[x]);
    s[x] ^= s[f[x]];
    return f[x] = tmp;
}

ll insert (ll x) {
    if (m.find(x) == m.end()) m[x] = ++cnt;
    return m[x];
}

int main() {
    while (scanf ("%lld%lld", &n, &q) != EOF) {
        char str[4];
        memset(f, -1, sizeof f);
        memset(s, 0, sizeof s);
        ll ans = q;
        for (register ll i = 1, u, v; i <= q; ++i) {
            scanf ("%lld%lld%s", &u, &v, str);
            if (ans < q) continue;
            u = insert(u - 1), v = insert(v);
            ll fu = find(u), fv = find(v);
            ll t = 0;
            if (str[0] == 'o') ++t;
            if (fu == fv) {  //root相等
                if (s[u] ^ s[v] != t)
                    ans = i - 1;
            } else { //一定有fu<fv(编号比较)
                f[fv] = fu;
                s[fv] = s[u] ^ s[v] ^ t;
                //矢量的异或运算
            }
        }
        printf ("%lld\n", ans);
    }
    return 0;
}