「CF2178G」deCH OR Dations

    「CF2178G」deCH OR Dations

    CF2178G

    圆环上有 2n2n 个等间距的点,按顺时针顺序标记为 1,2,…,2n1, 2, \dots, 2n。有 nn 条具有不同端点的弦,其中第 ii 条弦连接 ai,bia_i, b_i。现在按照顺序依次连接这 nn 条弦。

    每当连接完前 ℓ\ell 条弦以后,考虑这 ℓ\ell 条弦的任意非空子集 SS。设 SS 中元素的索引分别为 c1,c2,…,cmc_1, c_2, \dots, c_m,若对于所有的 1≤i<m1 \leq i < m,都满足弦 cic_i 与弦 ci+1c_{i + 1} 相交,则称 SS 为一条链。

    当且仅当,每一条弦在前 ℓ\ell 条弦的所有子集链中出现偶数次时,称这些弦是紧密连接的。

    对于 11 到 nn 的每一个 ℓ\ell,你都需要判断前 ℓ\ell 条弦是否紧密连接。

    数据范围:2≤n≤5×1052 \leq n \leq 5 \times 10^5,1≤ai<bi≤2n1 \leq a_i < b_i \leq 2n。

    时空限制:33s / 512512MiB。

    Solution

    设 fif_i 表示考虑了前 ii 条弦,以弦 ii 为结尾的链个数。由于我们只关心链个数的奇偶性,所以我们只需维护  mod  2\bmod \ 2 意义下的值即可。显然有转移

    fi=(⨁j<i,ok(j,i)=1fj)⊕1f_i = \left(\bigoplus_{j < i, \mathrm{ok}(j, i) = 1} f_j\right) \oplus 1

    其中 ok(j,i)\mathrm{ok}(j, i) 表示弦 jj 与弦 ii 是否相交。

    考虑维护 ff。由于异或有着出现偶数次相消的性质,维护一个树状数组,其中 aja_j 与 bjb_j 处均储存着 fjf_j 的值,那么转移的式子就只需要查询区间 [ai,bi][a_i, b_i] 内的异或和即可。因为任何与弦 ii 不相交的弦 jj,贡献只会计入 00 次或 22 次。

    更进一步,设 g(i,j)g(i, j) 表示考虑了前 ii 条弦,以弦 ii 为结尾且包含弦 jj 的情况下,链个数的奇偶性。

    设 hih_i 表示集合 {j:g(i,j)=1}\{ j : g(i, j) = 1 \},显然有转移(这里的异或 ⊕\oplus 是针对集合的)

    hi=(⨁j<i,ok(j,i)=1hj)⊕[fi=1]{i}h_i = \left(\bigoplus_{j < i, \mathrm{ok}(j, i) = 1} h_j\right) \oplus [f_i = 1]\{ i \}

    所以判断前 ℓ\ell 条弦是否紧密相连,只需要判断 ⊕i=1ℓhi\oplus_{i = 1}^{\ell} h_i 是否为空集即可。

    现在要考虑快速维护 hh。由于我们只需要判断集合是否为空集,可以考虑使用异或哈希!具体地,对 1,…,n1, \dots, n 中的每一个数映射到一个 6464 位大整数。对于一个集合来说,该集合的哈希值即为集合所有元素映射值的异或和。那么两个集合异或后的哈希值即为各自哈希值的异或。于是我们就可以沿用上述维护 ff 的方法来维护 hh。

    时间复杂度 O(nlog⁡n)\mathcal{O}(n \log n)。

    #include <bits/stdc++.h>
    
    using i64 = long long;
    
    using u64 = unsigned long long;
    
    #define debug(a) std::cout << #a << '=' << (a) << ' '
    
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    const int N = 500100;
    
    int n;
    
    struct BIT {
        int n;
        std::vector<u64> c;
    
        BIT() {}
        BIT(int _n) : n(_n) {
            c.assign(n + 1, {});
        }
    
        void add(int x, u64 y) {
            for (; x <= n; x += x & -x) {
                c[x] ^= y;
            }
        }
    
        u64 ask(int x) {
            u64 ans = 0;
            for (; x; x -= x & -x) {
                ans ^= c[x];
            }
            return ans;
        }
    };
    
    std::mt19937_64 mtrand{std::random_device{}()};
    
    void work() {
        std::cin >> n;
    
        BIT b1(n * 2), b2(n * 2);
    
        std::string ans;
        u64 H = 0;
        for (int i = 1; i <= n; i ++) {
            int x, y;
            std::cin >> x >> y;
    
            u64 f = b1.ask(x) ^ b1.ask(y) ^ 1;
            u64 h = b2.ask(x) ^ b2.ask(y);
            if (f) {
                h ^= mtrand();
            }
    
            H ^= h;
            ans += H ? "0" : "1";
    
            b1.add(x, f), b1.add(y, f);
            b2.add(x, h), b2.add(y, h);
        }
    
        std::cout << ans << '\n';
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        int T;
        std::cin >> T;
    
        while (T --) {
            work();
        }
    
        return 0;
    }