cf665e

摘要:
类似于数位dp的trie处理

正文:
One day, ZS the Coder wrote down an array of integers a with elements a1,  a2,  …,  an.

A subarray of the array a is a sequence al,  al  +  1,  …,  ar for some integers (l,  r) such that 1  ≤  l  ≤  r  ≤  n. ZS the Coder thinks that a subarray of a is beautiful if the bitwise xor of all the elements in the subarray is at least k.

Help ZS the Coder find the number of beautiful subarrays of a!

Input
The first line contains two integers n and k (1 ≤ n ≤ 106, 1 ≤ k ≤ 109) — the number of elements in the array a and the value of the parameter k.

The second line contains n integers ai (0 ≤ ai ≤ 109) — the elements of the array a.

Output
Print the only integer c — the number of beautiful subarrays of the array a.

Examples
input

3 1
1 2 3

output

5

input

3 2
1 2 3

output

3

input

3 3
1 2 3

output

2

给了一个序列,问存在多少这样的区间l,r,使得区间里所有元素xor和>=k。

数据1e6,当时猜了估计是数据结构…然而本人数据结构异常菜,仅会线段树,用线段树性质猜了一发,果然wa了。

正解是用trie处理,其实就是一个二叉树,首先trie可以添加元素,还可以记录该点的子节点元素个数。

再看着道题,我们如果预处理前缀xor和的话,区间l,r的xor可以用
indx[r] xor indx[l - 1]来得到,那么我们枚举到r的时候就是找前面有多少indx[l]使得indx[r] xor indx[l] >= k。

现在看这个trie树,从根到叶子节点是高位到低位,cur记录的是之前xor的和,第r个前缀,枚举到第i位的时候,如果 $ cur + 2^{i} >= k $那么跟第r个前缀第i位异或为1对应的节点的子节点全部满足,所以ans += 节点的子节点,然后把这位置为0,继续向下找。如果这位置为1,仍然没有k大,说明这一位必须置为1,因为后面所有置为1也没有这一位置为1的值大,然后更新cur,向下找。(这一段可以看代码,好理解一些)。

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<utility>
#include<sstream>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
const int emaxn = 37000000;
int logv,n,k;
int a[maxn],tot;
int ch[emaxn][2],cnt[emaxn];
void add(int x){
int root = 0;
cnt[root]++;
for(int i = logv;i >= 0;i--){
int temp = (x >> i)&1;
if(ch[root][temp] == -1){
ch[root][temp] = ++tot;
root = tot;
}
else
root = ch[root][temp];
cnt[root]++;
}
}
int work(int x){
if(x == -1)return 0;
return cnt[x];
}
ll query(int x){
int root = 0;
int cur = 0;
ll ans = 0;
for(int i = logv;i >= 0;i--){
if(root == -1)break;
int temp = (x >> i)&1;
if((cur | (1 << i)) >= k){
ans = ans + work(ch[root][temp^1]);
root = ch[root][temp];
}
else{
cur = cur | (1 << i);
root = ch[root][temp^1];
}
}
if(cur >= k)
ans = ans + work(root);
return ans;
}
int main()
{

#ifdef LOCAL
freopen("C:\\Users\\ΡΡ\\Desktop\\in.txt","r",stdin);
//freopen("C:\\Users\\ΡΡ\\Desktop\\out.txt","w",stdout);
#endif // LOCAL
logv = 30;
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;i++){
scanf("%d",&a[i]);
}
tot = 0;
memset(ch,-1,sizeof(ch));
memset(cnt,0,sizeof(cnt));
add(0);
int temp = 0;
ll ans = 0;
for(int i = 1;i <= n;i++){
temp = temp^a[i];
ans = ans + query(temp);
add(temp);
}
printf("%I64d\n",ans);
return 0;
}