Description

给定\(n\)个数，求其中前\(k\)大的区间异或和的和

Solution

首先区间异或和可以直接用前缀异或和化成两个数的异或值

从左到右建出可持久化\(01-Trie\)树

其实是不需要的，因为我们可以不考虑顺序的问题，求出前\(2k\)大，然后再除\(2\)

但是蒟蒻还是建了。。。

考虑先把每个右端点的第\(1\)大区间扔进\(pq\)

每次取出堆顶元素，更新答案，然后把相应的右端点的下一个排名的区间扔进\(pq\)

总复杂度应是\(O(n (\log n+\log k))\)

Code 

/*    可持久化01-trie并不是必要的    但是蒟蒻从来没写过，所以还是练练手吧    2019/4/11 Pac */#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define reg registerinline ll read(){    ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}const int MN=5e5+5,MK=2e5+5,MS=MN*65;int n,k;ll a[MN];struct Trie{int c[2],siz;}t[MS];int tot;int rt[MN];int Modify(int rt,int step,ll val){    int o=++tot;t[o]=t[rt];++t[o].siz;    if(step<0) return o;    if(val>>step&1) t[o].c[1]=Modify(t[o].c[1],step-1,val);    else t[o].c[0]=Modify(t[o].c[0],step-1,val);    return o;}ll Query(int x,int step,int k,ll val){    if(step<0) return 0;    bool tmp=val>>step&1;int ssiz=t[t[x].c[tmp^1]].siz;    if(k>ssiz) return Query(t[x].c[tmp],step-1,k-ssiz,val);    else return (1u<
     
       q;ll ans;int main(){    n=read();k=read();    reg int i;        rt[0]=Modify(rt[0],31,0);    for(i=1;i
      
       o.k) q.push((Node){o.r,o.k+1,Query(rt[o.r-1],31,o.k+1,a[o.r])});    }        return 0*printf("%lld\n",ans);}
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！