Codeforces 655E Beautiful Subarrays【01trie树】

题目链接：

http://codeforces.com/contest/665/problem/E

题意：

求异或值大于给定K的区间个数。

分析：

首先我们可以得到区间前缀的异或值。

这样我们将这个前缀M和K一起走trie树，如果该位K的值为0，那么无论怎么走最后得到的答案都不会比K小，所以直接加上另一边的子树大小，然后继续沿着当前边走。如果该位K的值为1，那么想要大于等于K必须沿着另一边贪心的走。

代码：

#include<cstdio>

#include<iostream>

using namespace std;

const int maxn = 1000000 << 5, maxm = 1e6 + 5;

int f[maxn][2];

int cnt = 1;

int son[maxn], pre[maxm];

long long ans = 0;

#define pl(n) cout<<#n<<": "<<n<<endl;

#define sa(n) scanf("%d", &n)

void insert(int n)

{

    int k;

    int u = 1;

    for(int i = 30; i >= 0; i--){

        k = (n >> i) & 1;

        if(!f[u][k]) f[u][k] = ++cnt;

        son[u]++;

        u = f[u][k];

    }

    son[u]++;

}

void query(int n, int m)

{

    int k1, k2, u = 1;

    for(int i = 30; i >= 0; i--){

        k1 = (n >> i) & 1;

        k2 = (m >> i) & 1;

        if(k2 == 0){

            ans += son[f[u][!k1]];

            u = f[u][k1];

        }

        else u = f[u][!k1];

        if(u == 0) break;

    }

    ans += son[u];

}

int main (void)

{

    int n,k;sa(n);sa(k);

    pre[0] = 0;

    int num;

    insert(pre[0]);

    for(int i = 1; i <= n; i++){

        sa(num);

        pre[i] = pre[i - 1] ^ num;

        query(pre[i], k);

        insert(pre[i]);

        //pl(ans);

    }

    printf("%I64d\n", ans);

    return 0;

}