CodeForces - 665E Beautiful Subarrays

Posted on | In , ,

思路

考虑将区间异或转换，我们处理一个异或前缀和数组，我们能够发现通过前缀和数组原来i-j的区间异或变成了pre[j]^pre[i-1]。然后我们逐个插入前缀和pre[i]，再由高到低逐个枚举k的二进制位:

  • 当k的第i位为1：显然我们要找一个使pre[i]异或后为1的数才能保证比k-1大。
  • 当k的第i位为0：如果我们找到一个使pre[i]异或后为1的数，那么异或后的数肯定比k-1大，我们直接在ans中加上这种数的个数（所以节点上要维护一个val次数数组），然后异或为1的不再考虑，我们进入异或后该位为0的节点。

对每个前缀和的答案累加就是最后的答案。

代码

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
#include <bits/stdc++.h>
#define ms(a,val) memset(a,val,sizeof(a))
#define ll long long
#define INF 0x7fffffff

using namespace std;

const int MAXN=1000005;
int pre[MAXN];
struct trie{
	int nodecnt,nexts[22*MAXN][2],val[22*MAXN];
	void init(){
		nodecnt=1;
		ms(nexts,-1);
	}
	int newnode(){
		val[nodecnt]=0;
		return nodecnt++;
	}
	void inserts(int n){
		int now=0;
		for(int i=30;i>=0;i--){
			int ch=(n>>i)&1;
			if(nexts[now][ch]==-1)nexts[now][ch]=newnode();
			now=nexts[now][ch];
			val[now]++;
		}
	}
	int query(int x,int y){
		int now=0,sum=0;
		for(int i=30;i>=0;i--){
			int t=(x>>i)&1,p=(y>>i)&1;
			if(p){
				if(nexts[now][!t]!=-1)now=nexts[now][!t];
				else break;
			}
			else{
				if(nexts[now][!t]!=-1)sum+=val[nexts[now][!t]];
				now=nexts[now][t];
			}
			if(now==-1)break;
		}
		return sum;
	}
}tree;

int main(){
	int n,k;
	while(~scanf("%d%d",&n,&k)){
		pre[0]=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&pre[i]);
			pre[i]^=pre[i-1];
		}
		tree.init();
		tree.inserts(0);
		ll sum=0;
		for(int i=1;i<=n;i++){
			sum+=(ll)(tree.query(pre[i],k-1));
			tree.inserts(pre[i]);
		}
		printf("%lld\n",sum);
	}
	return 0;
}