CF665E Beautiful Subarrays解题报告

解题报告

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;
}