AcWing 239 . 奇偶游戏

题目传送门

一、题目解析

维护前缀和，如果区间\([l, r]\)有偶数个\(1\)，那么\(s[r]\)和\(s[l-1]\)的奇偶性一定相同。如果区间\([l, r]\)有奇数个1，那么\(s[r]\)和\(s[l-1]\)的奇偶性一定不同。这样一来，维护区间信息就变成维护俩端点的信息了。

往广义的来说，并查集维护的是俩俩元素之间的信息。（这个信息，可以是是否联通，也可以是奇偶性是否相同，还可以是两点距离等等）

对于这一题，并查集维护的是俩元素间的奇偶性关系,\(d[x]\)表示\(x\)点与父亲的关系，\(0\)代表奇偶性相同，\(1\)代表奇偶性不同。那么显然每个点与根的奇偶关系就可以通过做路径上的边权做一遍异或即可。

二、带权并查集+离散化实现代码

#include 
using namespace std;
const int N = 20010;

int n, m;
int p[N], d[N];

//无序离散化
unordered_map S;
int get(int x) {
    if (S.count(x) == 0) S[x] = ++n; // x映射为第n个数字
    return S[x];
}
//带边权更新并查集模板
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() {
    cin >> n >> m;                        // n:01序列长度 m:问题数量
    n = 0;                                //序列的长度没有用处，我们只关心每个a,b范围内的数字1的个数
    for (int i = 1; i < N; i++) p[i] = i; //初始化并查集

    int res = m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        string type;
        cin >> a >> b >> type; // a~b之间1是奇数个还是偶数个
        a = get(a - 1), b = get(b);
        int t = 0;                //偶数个1
        if (type == "odd") 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] + t + d[b]) % 2; //这个式子的推导可以看一下其它我写的题解的图示
        }
    }
    cout << res << endl;
    return 0;
}

三、扩展域版本的并查集实现代码

#include 
using namespace std;

const int N = 40010, Base = N / 2;

//简化版本的食物链
int n, m;
//无序离散化
unordered_map S;
int get(int x) {
    if (S.count(x) == 0) S[x] = ++n;
    return S[x];
}
//并查集
int p[N];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;
    n = 0;
    for (int i = 1; i < N; i++) p[i] = i;

    int res = m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        string type;
        cin >> a >> b >> type;
        a = get(a - 1), b = get(b); //计算出新的在并查集中的号

        if (type == "even") {                //偶数个1
            if (find(a + Base) == find(b)) { //如果奇偶性不同，因为b与a+Base相同
                res = i - 1;
                break;
            }
            // join两个奇偶相同的集合
            p[find(a)] = find(b);
            p[find(a + Base)] = find(b + Base);
        } else { //奇数个1
            if (find(a) == find(b)) {
                res = i - 1;
                break;
            }
            // join两个奇偶不相同的集合
            p[find(a + Base)] = find(b);
            p[find(a)] = find(b + Base);
        }
    }
    cout << res << endl;
    return 0;
}