题解 CF665E 【Beautiful Subarrays】

whiteqwq · 2020-10-17 17:42:19 · 题解

CF665E Beautiful Subarrays解题报告：

更好的阅读体验

题意

• 给定一个长度为n的序列a，求有多少个子序列的异或和大于等于k；
• 序列的异或和为序列中所有数异或起来的结果。
• 数据范围：1\leqslant n\leqslant 10^6,1\leqslant a_i,k\leqslant 10^9。

分析

自己想出了做法，鸡冻。

首先根据异或的性质，求出异或的前缀和，把异或和转化为有多少个数对满足异或起来大于等于k（其中数对需要在异或前缀和数组中）。

然后我们对异或前缀和数组建一颗\text{01trie}，并求出每个点子树中终止点的个数size_x（终止点就是\text{01trie}插入时最后一个点），查询的时候按位查询。

具体地，我们对于每一位分类讨论，设第i位x为y，第i位k为p（y,p\in\{0,1\}），假如我们前i位与k都相同：

• 如果p=1，那么异或起来必须为1，直接跳一个y\oplus p；
• 如果p=0，那么异或起来可以是1可以是0，不难发现异或起来为1的情况一定全部满足答案，因此我们加上跳到y\oplus 1的所有情况size，并跳一个y\oplus p来循环计算异或起来为0的贡献。

  long long calc(int x,int k){
  int now=root;
  long long res=0;
  for(int i=30;i>=0;i--){
      int y=((x>>i)&1),p=((k>>i)&1);
      if(p==0)
          res+=1ll*size[chd[now][y^1]];
      now=chd[now][y^p];
  }
  res+=size[now];
  return res;
  }

但是这样并不行，因为我们提前把\text{01trie}建出来了，这样会两个异或起来不能成为一个区间的数的贡献加进答案。

可以边修改边查询，把\text{insert}直接改成经过的所有点都增加size，在每一次查询前插入上一个前缀和，这样我们可以保证查询的所有贡献都是有效的了。

复杂度O(n\log \max\{k,maxa\})。

代码

记得开\text{long long}。

#include<stdio.h>
const int maxn=1000005,maxk=30;
int n,k,tot,root;
int a[maxn],sum[maxn],chd[maxn*maxk][2],size[maxn*maxk];
long long ans;
void insert(int x){
    int now=root;
    for(int i=30;i>=0;i--){
        int y=((x>>i)&1);
        if(chd[now][y]==0)
            chd[now][y]=++tot;
        size[now]++,now=chd[now][y];
    }
    size[now]++;
}
long long calc(int x,int k){
    int now=root;
    long long res=0;
    for(int i=30;i>=0;i--){
        int y=((x>>i)&1),p=((k>>i)&1);
        if(p==0)
            res+=1ll*size[chd[now][y^1]];
        now=chd[now][y^p];
    }
    res+=size[now];
    return res;
}
int main(){
    root=tot=1;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]^a[i];
    }
    for(int i=1;i<=n;i++){
        insert(sum[i-1]);
        ans+=calc(sum[i],k);
    }
    printf("%lld\n",ans);
    return 0;
}