Educational Codeforces Round 12 E. Beautiful Subarrays

布满荆棘的人生 2022-08-21 07:52 21阅读 0赞

题意：  
问有多少个连续区间异或和大于等于k

思路：  
sum\[l,r\]= sum\[1,l-1\] ^ sum\[1,r\]

所以记录异或前缀和，并用字典树维护

从高位开始插入，num维护有多少**数的前缀**等于插入路径的，只要高位异或大于等于k，则之后肯定满足；否则，必须将cur的那一位置为1，然后继续。

（因为退役已久，写了一发样例都没过，于是改着改着就改成codeforces的tutorial的样子，最后发现是我从低位开始插入的）

#include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int MAX = 31;
    const int MAXN = 1e6 + 5;
    const int MAXM = MAX * MAXN;
    int num[MAXM];
    int ne[MAXM][2];
    int cnt;
    int n, k;
    
    ll query(int x)
    {
        int v = 0;
        ll ans = 0;
    
        auto getCnt = [](int v){
       return v == -1 ? 0 : num[v];};
    
        int cur = 0;
        for(int i = 30; i >=0; i--)
        {
            if (v == -1) break;
            int b = (x >> i) & 1;
            if((cur | (1 << i)) >= k)
            {
                ans += getCnt(ne[v][b ^ 1]);
                v = ne[v][b];
            }
            else
            {
                v = ne[v][b ^ 1];
                cur |= (1 << i);
            }
        }
        if (cur >= k) ans += getCnt(v);
        return ans;
    }
    void ins(int x)
    {
        int u = 0;
        for(int i = 30 ; i >=0 ; i--)
        {
            int j = (x >> i) & 1;
            if(ne[u][j] == -1) ne[u][j] = ++cnt;
            u = ne[u][j];
            num[u]++;
        }
    }
    int main()
    {
        while(scanf("%d%d", &n, &k) != EOF)
        {
            memset(num, 0, sizeof num);
            memset(ne, -1, sizeof ne);
            long long ans = 0;
            cnt = 0;
            int sum = 0;
            ins(0);
            for(int i = 0, u ; i < n ; i++)
            {
                scanf("%d", &u);
                sum ^= u;
                ans += query(sum);
                ins(sum);
            }
            printf("%I64d\n", ans);
        }
        return 0;
    }