自动搬运

查看原文

来自洛谷，原作者为

	qwaszx 不再为往事受困.

搬运于2025-08-24 22:09:01，当前版本为作者最后更新于2019-04-08 20:38:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

神仙们都写的可持久化$Trie$然而我并不会写

给一个简单的做法好了QAQ

首先做前缀异或和，然后变成求最大的$k$对异或和的和

注意到这是一个关于三角$(a_i\ xor\ a_j,0\leq i\leq j\leq n)$的求值，并且有$a_i\ xor\ a_j=a_j\ xor\ a_i$所以我们先把答案乘二然后再除回去，这样我们要求的就是最大的$2k$个有序对，这个就很好处理了.对角线上的元素并不影响，因为$a_i\ xor\ a_i=0$是最小的.

可以对每一个$i$求出第$t$(初始为$1$)大的$a_i\ xor\ a_j$，然后把结果扔到堆里，每次取堆顶，然后把堆顶对应的$i$的第$t+1$大的$a_i\ xor\ a_j$扔进堆里.具体看代码好了QAQ.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=20000000+10;
struct Node{int id,rk;long long w;bool operator <(const Node &a)const{return w<a.w;}};
priority_queue<Node>q;
long long ans=1,x,s[N];
int a[N][2],size[N],n,m,tot;
void ins(long long x)
{
    int u=0;
    for(int i=31;i>=0;i--)
    {
        int ch=(x>>i)&1;size[u]++;//插入的时候维护子树大小便于处理
        if(!a[u][ch])a[u][ch]=++tot;
        u=a[u][ch];
    }
    size[u]++;
}
long long query(long long x,int rk)
{
    int u=0;long long ans=0;
    for(int i=31;i>=0;i--)
    {
        int ch=(x>>i)&1;//cout<<u<<" "<<ch<<" "<<size[a[u][1]]<<"  ";
        if(!a[u][ch^1])u=a[u][ch];//如果没有和这一位相异的就直接走
        else if(rk<=size[a[u][ch^1]])u=a[u][ch^1],ans|=1LL<<i;//看一下相异节点的子树大小决定走哪边.和平衡树的操作差不多
        else rk-=size[a[u][ch^1]],u=a[u][ch];
    }
    return ans;
}
long long getin()//不开long long见祖宗 我就见祖宗了QAQ
{
    long long x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x;
}
int main()
{
    n=getin(),m=getin();m<<=1;//前2k个
    for(int i=1;i<=n;i++)x=getin(),s[i]=s[i-1]^x;
    for(int i=0;i<=n;i++)ins(s[i]);//注意有0
    for(int i=0;i<=n;i++)q.push((Node){i,1,query(s[i],1)});//堆中节点存第rk大的s[id]^s[j]
    for(int i=1;i<=m;i++)
    {
        Node t=q.top();ans+=t.w;q.pop();//cout<<t.id<<" "<<t.rk<<" "<<t.w<<endl;
        if(t.rk<n)q.push((Node){t.id,t.rk+1,query(s[t.id],t.rk+1)});
    }
    cout<<(ans>>1)<<endl;//最后把答案除以二
}

可以看到这个代码只有几十行，但是跑得很快.

最后一定一定要开$long\ long$啊$QAQ$.