洛谷 P5283 【十二省联考2019】异或粽子 题解

洛谷 P5283 【十二省联考2019】异或粽子题解

2020-02-03 xiaoh

题意

给定一个有\(n\)个数的序列\(a\)(\(1\leq n \leq 5×10^5,1 \leq a_i \leq 4294967295\))，求这个序列中前\(k\)大的异或区间和之和。(\(1\leq k \leq 2×10^5\))

题解

看到“异或”和“区间和”，不难想到用可持久化Trie来维护整个序列的前缀和。接下来考虑如何求出前k大的元素。这让我们想到了洛谷 P1631 序列合并。我们可以以每个\(i\)∈ \([1,n]\) 作为区间的r，借助可持久化Trie求出使异或和最大的l并放入堆。接下来依次取出堆顶，不妨设其对应的区间为 \([l_x,r_x]\),且为对应\(r_x\)的所有左区间的第\(k_x\)大，那么我们就求出对应\(r_x\)的第\(k_x+1\)大元素并放入堆即可，很明显，这是可持久化Trie可以做到的。时间复杂度\(O(kWlogn)\)(\(W\)为位宽)。

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
    x=0;
    int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    x*=f;
    return;
}
template<typename T>
void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>=10) write(x/10);
    putchar(x%10+'0');
    return;
}
const int MAXN=500010,W=33;
int n,k;
long long a[MAXN];
long long s[MAXN];
int tot=0;
int trie[MAXN*(W+1)*2][2];
int rt[MAXN];
int sz[MAXN*(W+1)*2];
void insert(int x,int k,int p,int q)
{
    if(k<0)
    {
        sz[q]++;
        return;
    }
    int c=(s[x]>>k)&1;
    trie[q][c^1]=trie[p][c^1];
    trie[q][c]=++tot;
    sz[trie[q][c]] = sz[trie[p][c]];
    insert(x,k-1,trie[p][c],trie[q][c]);
    sz[q]=sz[trie[q][0]]+sz[trie[q][1]];
}
void query(int p,long long x,int k,int rk,long long &ans)
{
    if(k<0) return;
    int c=(x>>k)&1;
    if(sz[trie[p][c^1]]>=rk) ans=(ans<<1)|1,query(trie[p][c^1],x,k-1,rk,ans);
    else ans<<=1,query(trie[p][c],x,k-1,rk-sz[trie[p][c^1]],ans);
}
struct node{
    long long x;
    int rk,id;
    friend bool operator <(node a,node b)
    {
        return a.x<b.x;
    }
};
priority_queue<node> q;
long long ans=0;
int main()
{
    read(n),read(k);
    sz[0]=0;
    rt[0]=++tot;
    insert(0,W,0,rt[0]);
    for(int i=1;i<=n;i++) read(a[i]),s[i]=s[i-1]^a[i];
    for(int i=1;i<=n;i++)
    {
        long long tmp=0;
        rt[i]=++tot;
        insert(i,W,rt[i-1],rt[i]);
        query(rt[i],s[i],W,1,tmp);
        q.push({tmp,1,i});
    }
    for(int i=1;i<=k;i++)
    {
        node tmp=q.top();q.pop();
        ans+=tmp.x;
        long long x=0;
        query(rt[tmp.id],s[tmp.id],W,tmp.rk+1,x);
        q.push({x,tmp.rk+1,tmp.id});
    }
    write(ans),putchar('\n');
    return 0;
}

洛谷 P5283 【十二省联考2019】异或粽子 题解

原文：https://www.cnblogs.com/xiaoh105/p/12256710.html