CF665E Beautiful Subarrays（Tire）

一个经典套路是异或前缀和公式，因此我们可以枚举右端点，寻找异或值大于等于k的答案

做完后每次把前缀和放到trie树上面去。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;
const int M=N*31;
int n,k,a[N],tr[M][2],tot=1,siz[M];
ll ans;
void insert(int x) {
    int u=1;
    for(int i=30;~i;--i) {
        int c=x>>i&1;
        if(!tr[u][c])tr[u][c]=++tot;
        u=tr[u][c],++siz[u];
    }
}
int query(int x) {
    int u=1,res=0,i;
    for(i=30;~i;--i) {
        int c=x>>i&1;
        if(k>>i&1)u=tr[u][!c];
        else res+=siz[tr[u][!c]],u=tr[u][c];
    }
    res+=siz[u];
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i)a[i]^=a[i-1];
    for(int i=1;i<=n;++i)insert(a[i-1]),ans+=query(a[i]);
    printf("%lld
",ans);
    return 0;
}