题解：P5937 [CEOI1999] Parity Game

· · 题解

一种不用种类 / 扩展域并查集的做法。因为我不会

首先，给定一个区间的奇偶性，那么相当于给定前缀和数组 sum_{l - 1},sum_r 的奇偶性关系。如果该区间和为偶数，那么 sum_l\equiv sum_r \pmod{2} 。如果该区间和为奇数，那么 sum_l \equiv sum_r + 1 \pmod{2} 。如果不合法了，那么一定是奇偶性关系矛盾了，可以想到用并查集去维护。

但是呢，并查集只能维护相等的联通块，对于不等的情况如何处理？

我们发现，如果 sum_i 与 sum_0 没有给定奇偶性关系，那么其奇偶性是未知的，那么对于不等情况，除非 sum_{l - 1}, sum_r 奇偶性确认相等，那么一定可以构造出奇偶关系。但是，如果在之后的询问中确定了 sum_{l - 1} 或 sum_{r} 的奇偶关系，那么此时还需要重新判断两个点的奇偶关系是否不等。

为了处理这个问题，我们不妨对于有不等关系的联通块之间连边，如果某个点的奇偶性确定了，那么就可以通过这些边进行遍历，把所有与其确认关系的点的奇偶性确定。每次合并把确认的奇偶性下放。

那么如果对于查询的两个点，两个点的奇偶性与给定奇偶性矛盾，那么就得到答案了。

注意对于相等关系，合并时要把边集也合并了。

每次下放时间复杂度 O(m)，合并时间复杂度 O(m)，总时间复杂度 O(m ^ 2)，有一定常数，注意需要离散化。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1e4 + 10;
typedef long long ll;
typedef pair<int, int> pi;
int n, m;
int f[N], col[N];
int find (int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}
vector<int> lsh;
int ql[N], qr[N], typ[N];
vector<int> g[N];
void updata (int x, int from) {
    for (auto v : g[x]) {
        v = find(v);
        if (v == from) continue;
        if (col[v] == (col[x] ^ 1)) continue; // 这样快一点
        col[v] = col[x] ^ 1;
        updata(v, x);
    }
}
void merge (int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    for (auto v : g[fx]) { // 实际上可以启发式合并优化一下
        g[fy].push_back(v);
    }
    g[fx].clear();
    sort(g[fy].begin(), g[fy].end());
    g[fy].erase(unique(g[fy].begin(), g[fy].end()), g[fy].end());
    if (col[fx] != -1) col[fy] = col[fx];
    f[fx] = fy;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    f[0] = 0, col[0] = 0;
    lsh.push_back(0);
    for (int i = 1; i <= m; i ++) {
        int l, r;
        string t;
        cin >> l >> r >> t;
        lsh.push_back(l - 1), lsh.push_back(r);
        ql[i] = l, qr[i] = r, typ[i] = (t == "even" ? 0 : 1);
    }
    sort (lsh.begin(), lsh.end());
    lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
    for (int i = 1; i <= m; i ++) ql[i] = lower_bound(lsh.begin(), lsh.end(), ql[i] - 1) - lsh.begin(), qr[i] = lower_bound(lsh.begin(), lsh.end(), qr[i]) - lsh.begin();
    for (int i = 0; i < lsh.size(); i ++) f[i] = i, col[i] = -1;
    col[0] = 0;
    for (int i = 1; i <= m; i ++) {
        int l = find(ql[i]), r = find(qr[i]);
        if (typ[i]) {
            if (col[l] != -1) updata(l, -1);
            if (col[r] != -1) updata(r, -1);
            if (l == r || (col[l] != -1 && col[r] != -1 && col[l] == col[r])) {
                cout << i - 1;
                return 0;
            }
            g[l].push_back(r), g[r].push_back(l);
        } else {
            if (col[l] != -1) updata(l, -1);
            if (col[r] != -1) updata(r, -1);
            if (col[l] != -1 && col[r] != -1 && col[l] != col[r]) {
                cout << i - 1;
                return 0;
            }
            merge(l, r);
        }
    }
    cout << m << endl;
    return 0;
}