【Codeforces 665E-Beautiful Subarrays】01字典树

Beautiful Subarrays

题目链接：

https://codeforces.com/contest/665/problem/E

Description

Input

Output

##Sample Input

3 1
1 2 3

##Sample Output

5

题意

给出一个数组，找出有多少个连续子序列满足子序列中所有元素的异或和大于等于k。

题解：

首先把连续子序列的异或和变成两个位置前缀和的异或和。
这样就相当于对于某个异或前缀和，看他之前的异或前缀和有多少个与他异或的结果大于等于k。
这个过程我们只要用01字典树就可以解决。

注意01字典树中一定要判断下一个节点是否存在再进行算贡献和递归。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define dbg(x) cout<<#x<<" = "<<x<<endl
#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl
#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl
typedef long long ll;
const int maxn =1e6+10;
int cnt[maxn*30];
int nt[maxn*30][2];
int tot=1;
int a[maxn],b[maxn];
map<int,int> mp;
void Insert(int a,int st,int rt)
{
    cnt[rt]++;if(st==-1) return ;int po=(a>>st)&1;if(!nt[rt][po]) nt[rt][po]=tot++;Insert(a,st-1,nt[rt][po]);
}
int Find(int rt,int st,int k,int num)
{
    if(st==-1) return 0;int A=((k>>st)&1);int B=((num>>st)&1);int ans=0;if(A==1){
    if(B==1){
    if(nt[rt][0]) ans=ans+Find(nt[rt][0],st-1,k,num);}else{
    if(nt[rt][1]) ans=ans+Find(nt[rt][1],st-1,k,num);}}else{
    if(B==1){
    if(nt[rt][0]) ans=ans+cnt[nt[rt][0]];if(nt[rt][1]) ans=ans+Find(nt[rt][1],st-1,k,num);}else{
    if(nt[rt][1]) ans=ans+cnt[nt[rt][1]];if(nt[rt][0]) ans=ans+Find(nt[rt][0],st-1,k,num);}}return ans;
}
int main()
{
    //freopen(".in","r",stdin);int n,k;scanf("%d%d",&n,&k);Insert(0,30,0);mp[0]++;int pre=0;ll ans=0;for(int i=1;i<=n;i++){
    int x;scanf("%d",&x);pre=(pre^x);ans=ans+Find(0,30,k,pre);ans=ans+mp[pre^k];mp[pre]++;Insert(pre,30,0);}printf("%lld\n",ans);return 0;
}