RT,用的 01trie,query 函数和题解实现的不一样,查询的是有多少个数异或上 num>=k,但是 WA on #6,求大佬帮忙看看。
#include<bits/stdc++.h>
#define re register
#define il inline
#define ll long long
//define int long long
#define pii pair<int,int>
#define ls ((p)<<1)
#define rs (((p)<<1)|1)
#define mid ((l+r)>>1)
#define lowbit(x) ((x)&(-(x)))
#define printc cerr<<"-------------------------\n"
#define yon(x) (x?cout<<"Yes\n":cout<<"No\n")
#define YoN(x) (x?cout<<"YES\n":cout<<"NO\n")
#define rep(x,a,b) for(re int (x)=(a);(x)<=(b);++(x))
#define per(x,a,b) for(re int (x)=(a);(x)>=(b);--(x))
#define dbg(x) cerr<<#x<<":"<<x<<" "
#define cend cerr<<'\n'
#define fsp(x) fixed<<setprecision(x)
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define inf 0x3f3f3f3f
#define maxn 1001010
#define mod 0
constexpr int D=30;
int n,k;
int a[maxn],pre[maxn];
int tot=1;
struct trie{
struct tree{
int son[2];
int cnt;
}t[maxn<<5];
void insert(int num){
int now=1;
per(i,D,0){
int bit=(num>>i)&1;
if(!t[now].son[bit])t[now].son[bit]=++tot;
now=t[now].son[bit];
++t[now].cnt;
}
}
int query(int num){
int now=1,res=0;
per(i,D,0){
int bit=(num>>i)&1;
if((num|(1<<i))<k)return res;
res+=t[t[now].son[bit^1]].cnt;
num^=(bit<<i);
now=t[now].son[bit];
}
return res;
}
}T;
ll ans;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>k;
T.insert(0);
rep(i,1,n){
cin>>a[i];
pre[i]=pre[i-1]^a[i];
T.insert(pre[i]);
ans+=T.query(pre[i]);
}
cout<<ans;
return 0;
}
/*
input:
output:
*/