每日一题 CF665E Beautiful Subarrays 题解

这题还是有点新意的，套路部分就不讲了，我们套路前缀和，然后就知道要用一个trie树这样的东西来维护一下，如果有人这里不是
很熟可以看一下我之前写的https://blog.nowcoder.net/n/744869ac01154d47b1240cfaebc3839e
接着我们来看一下如何处理，我们有点像是在trie上统计若干的子树的sz和，这样的一个二分的过程
我们来看具体维护，我们考虑当前是在第k位，然后当前val的第k位是x，K的第k为是y
那么如果y是0
那么我们相当于对于xor val的这一位就有两种选择
其中如果异或出来是1的那种选法我们无论底下怎么选都是满足条件的
反之我们就必须只有一种选法。
具体可以看代码，然后我们还需要加上最后到达的节点的sz，这个是刚好等于K的个数。

代码：

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ------------------------------------------------ "<<endl
#define LL long long
#define DB double
#define mpt make_pair
#define pb push_back
inline int read(){
    int nm=0; bool fh=true; char cw=getchar();
    for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
    for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
    return fh?nm:-nm;
}
#define M 1000200
int n,K,tot,all; LL ans;
int sz[M<<5],ch[M<<5][2];
inline void ins(){
    int nw=1;
    for(int k=30,t;~k;--k){
        t=(all&(1<<k))>0;
        if(!ch[nw][t]) ch[nw][t]=++tot;
        nw=ch[nw][t],++sz[nw];
    }
}

int main(){
    n=read(),K=read(),tot=1,ins();
    for(int i=1,x;i<=n;i++){
        x=read(),all^=x; int nw=1;
        for(int k=30,t,tk;~k;--k){
            t=(all&(1<<k))>0,tk=(K&(1<<k))>0;
            if(!tk) ans+=(LL)sz[ch[nw][t^1]];
            nw=ch[nw][t^tk];
        }
        ans+=(LL)sz[nw],ins();
        //debug(i)sp,debug(ans)el;

    } printf("%lld\n",ans);
    return 0;
}