CF2178G deCH OR Dations 题解

Mier_Samuelle · 2025-12-29 21:00:24 · 题解

使用经典的异或哈希。给每条弦赋一个随机的权值 w_i，并定义每条链的权值为链上所有弦的权值异或和，则只需判断所有链的权值的异或和是否为 0。

接下来考虑怎么做这个东西。定义 f_i 为以弦 i 结尾的链的权值的异或和，g_i 为以弦 i 结尾的链的个数的奇偶性。则转移为

变一下形，变为

现在，转移变成了 f_j 的异或和和 g_j 的异或和两部分。树状数组维护即可。

复杂度 O(n \log n)。

:::success[代码]

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 1e6 + 10;
mt19937_64 rd(time(0)); 
int a[MAXN], b[MAXN], n;
struct Fenwick{
    ull val[MAXN];
    void clear(){
        for (int i = 1; i <= 2 * n; i++){
            val[i] = 0;
        }
        return;
    }
    ull lowbit(ull x){
        return x & -x;
    }
    void modify(int u, ull x){
        while (u <= 2 * n){
            val[u] ^= x;
            u += lowbit(u);
        }
        return;
    }
    ull query(int u){
        ull res = 0;
        while (u){
            res ^= val[u];
            u -= lowbit(u);
        }
        return res;
    }
}f, g;
void solve(){
    cin >> n;
    ull ans = 0;
    f.clear();
    g.clear();
    for (int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
        ull pf = f.query(a[i]) ^ f.query(b[i]);
        ull pg = g.query(a[i]) ^ g.query(b[i]);
        ull w = rd();
        ull nf = pf ^ ((pg & 1) * w) ^ w;
        ull ng = pg ^ 1;
        f.modify(a[i], nf);
        f.modify(b[i], nf);
        g.modify(a[i], ng);
        g.modify(b[i], ng);
        ans ^= nf;
        cout << (ans == 0 ? '1' : '0');
    }
    cout << endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--){
        solve();
    }
    return 0;
}

:::