E. Beautiful Subarrays(Trie维护前缀异或和)

思路:看题,不难知道要做前缀和.枚举$r$,我们需要一种数据结构,得知前缀异或和中有多少$l<r,pr{e}_r\oplus pr{e}_{l-1}>=k$.
前缀异或和,这是一个01Trie树的经典运用.异或和相关的问题可以用Trie01树维护,具体思想就是把一个数字的二进制形式看成01的字符串,每个数字就转化成一个长度为30~60的01字符串.
在这题中,我们从高向低建树,当$k$的第$i$位是0时,$pr{e}_r\oplus pr{e}_{l-1}$第$i$位两个位置都可以取,取0就是继续往Trie树向下走,取1就是立马结算贡献.
当k第i位是1时,显然$pr{e}_r\oplus pr{e}_{l-1}$只能取1。
式子中$pr{e}_r\oplus pr{e}_{l-1}$,$pr{e}_r$事实上是一个定值,根据需要的,取$pr{e}_{l-1}$即可,而$pr{e}_{l-1}$取值决定了怎么继续向Trie向下走.

#include
using namespace std;
const int maxn = 1000005;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];
//前向星
// for(int i=head[u];i!=-1;i=nxt[i]) v = to[i]
//int nxt[maxn],head[maxn],to[maxn];// head[u],cnt 初始值是-1
//int tot = -1;
//void add(int u,int v){
//	nxt[++tot] = head[u];
//	head[u] = tot;
//	to[tot] = v;
//}
int tr[maxn*30][2];int cnt[maxn*30];int idx = 1;
void insert(int x){
	int p = 1;
	for(int i=30;i>=0;i--){
		int c = (x>>i&1);
		if(!tr[p][c]) tr[p][c] = ++idx;
		p = tr[p][c];
		cnt[p]++;
	}
}
int query(int x,int k){
	int p = 1;// x is pre_r
	int res = 0;
	for(int i=30;i>=0;i--){
		int c = (x>>i&1);
		if(k>>i&1)  p = tr[p][c^1];//k是1,pre_r ^ pre_l=1,那么此时c取pre_r相反数字,且不能统计答案,因为还没有确定后续状态
		else res+=cnt[tr[p][c^1]],p =tr[p][c];
		//k是0,pre_r ^ pre_l可取0可取1,取0继续往下走,取1马上统计出pre_r^pre_l > 1的答案
	}
	//等于pre_r ^ pre_l == k的情况
	res +=cnt[p];
	return res;
}
int a[maxn];
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,k;
	cin>>n>>k;
	a[0] = 0;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) a[i]^=a[i-1];
	ll ans = 0;
	for(int i=1;i<=n;i++){
		insert(a[i-1]);
		ans+=query(a[i],k);
	}
	cout<<ans;
}
/*
1 1
1
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62