[CF665E] Beautiful Subarrays - 字典树,贪心

Description

给定长度为 \(n\) 的序列 \(\{a_i\}\)，给定 \(k\)，求有多少个子序列满足 \(\oplus_{i=l}^r a_i \ge k\)。

Solution

处理出前缀异或和序列，枚举 \(s_{l-1}\)，要求 \(s_{l-1} \oplus s_r \ge k\)，Trie 树上边跑边统计即可

具体地，当 \(k \oplus s_{l-1}\) 的某一位是 \(1\) 的时候，我们只能走这一边，直接继续往下走；当 \(k\) 的某一位是 \(0\) 的时候，\(1\) 的整个子树会产生贡献，于是我们记录这个贡献，并继续往 \(0\) 的那一边走即可

具体地，当 \(k\) 的某一位是 \(1\) 时，我们只能走与 \(s_{l-1}\) 的这一位相反的那一边，直接继续往下走即可

当 \(k\) 的某一位是 \(0\) 的时候，与 \(s_{l-1}\) 的这一位相反的那一边的整个子树都会产生贡献，于是我们记录这个贡献，并继续往相同的那一边走即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define newNode &nodebuf[++cnt]
const int N = 1000005;

struct Node
{
    Node *ch[2];
    int size;

    Node()
    {
        size=0;
        ch[0]=ch[1]=0;
    }
} nodebuf[N*30];

int cnt;

Node root;

void insert(int x)
{
    Node *p=&root;
    for(int i=31;i>=0;--i)
    {
        p->size++;
        if((x>>i)&1)
        {
            if(p->ch[1]==0)
            {
                p->ch[1]=newNode;
            }
            p=p->ch[1];
        }
        else
        {
            if(p->ch[0]==0)
            {
                p->ch[0]=newNode;
            }
            p=p->ch[0];
        }
    }
    p->size++;
}

int calc(int x,int u)
{
    int ans=0;
    Node *p=&root;
    int i;
    for(i=31;i>=0 && p;--i)
    {
        if((x>>i)&1)
        {
            p=p->ch[((u>>i)&1)^1];
        }
        else
        {
            if(p->ch[((u>>i)&1)^1])
            {
                ans+=p->ch[((u>>i)&1)^1]->size;
            }
            p=p->ch[((u>>i)&1)];
        }
    }
    if(i==-1 && p) ans+=p->size;
    return ans;
}

int n,k,t1,t2,a[N];

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        a[i]^=a[i-1];
    }
    int ans=0;
    for(int i=n;i>=1;--i)
    {
        insert(a[i]);
        //cout<<"doing i="<<i<<endl;
        ans+=calc(k,a[i-1]);
        //cout<<"ans="<<ans<<endl;
    }
    cout<<ans<<endl;
}

[CF665E] Beautiful Subarrays - 字典树,贪心

原文：https://www.cnblogs.com/mollnn/p/13615662.html