【trie树】CF Edu12 E

﹏ヽ暗。殇╰゛Y 2024-03-08 05:08 89阅读 0赞

[Problem - E - Codeforces][]

题意：

![50a6b890c52f4514a6443577a8f2f70b.png][]

思路：

这其实是一个套路题

区间异或转化成前缀异或，然后枚举 i

对于每一个 i，ai ^ x = k，对 x 计数

先建一棵字典树，然后在字典树上计数

先去对 > k 的部分计数，再对 = k 的部分计数

如果 k 的第 j 位是1，那么沿着走就行，否则对 (k >> j & 1) ^ 1的部分计数，然后继续沿着走

最后的res += cnt\[p\]是对 = k 的部分计数

Code：

#include <bits/stdc++.h>
    
    using i64 = long long;
    
    constexpr int N = 1e6 + 10;
    constexpr int M = 1e6 + 10;
    constexpr int P = 2600;
    constexpr i64 Inf = 1e18;
    constexpr int mod = 1e9 + 7;
    constexpr double eps = 1e-6;
    
    int n, k;
    int tot = 1;
    int a[N], cnt[N * 30];
    int tr[N * 30][2];
    
    void insert(int x) {
        int p = 1;
        for (int j = 30; j >= 0; j --) {
            int u = (x >> j) & 1;
            if (!tr[p][u]) tr[p][u] = ++tot;
            p = tr[p][u];
            cnt[p] ++;
        }
    }
    i64 query(int x, int y) {
        int p = 1;
        i64 res = 0;
        for (int j = 30; j >= 0; j --) {
            int u = (x >> j) & 1, v = (y >> j) & 1;
            if (v) {
                p = tr[p][u ^ 1];
            }else {
                res += cnt[tr[p][u ^ 1]];
                p = tr[p][u];
            }
        }
        res += cnt[p];
        return res;
    }
    void solve() {
        std::cin >> n >> k;
        for (int i = 1; i <= n; i ++) std::cin >> a[i];
        for (int i = 1; i <= n; i ++) a[i] ^= a[i - 1];
    
        i64 ans = 0;
        for (int i = 1; i <= n; i ++) {
            insert(a[i - 1]);
            ans += query(a[i], k);
        }
    
    
        std::cout << ans << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - E - Codeforces]: https://codeforces.com/contest/665/problem/E
[50a6b890c52f4514a6443577a8f2f70b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/08/34cffa3c390f40b39167f026aa15aeb6.png