# [[十二省联考2019]异或粽子](<https://www.luogu.org/problemnew/show/P5283>)

先吐槽一下,在考场上完全没有将这道题和超级钢琴联系起来,然后$GG$,喜提$60$走人

赛后听说直接上可持久化$Trie$用堆维护就好了

然后自己回来又打开了超级钢琴.

这道题就有思路了

------

很明显,这道题我们可以利用前缀和优化到最大的$k$对数的异或和

我们想对于每一个$i$，我们在$0—i-1$去查阅它的异或最大值,用可持久化$Trie$可以办到,统计完答案及答案所在位置(设为$ans_{pos}$)后将该区间分裂为$0—ans_{pos - 1}$和$ans_{pos + 1}—i -1$

剩下的以此类推，放到堆里去维护就好了

当然,因为异或第零个数比较麻烦,我将$rt$数组整体右移了一位。

```c++
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cctype>
#include<algorithm>
#include<queue>
#define LL long long
#define pii pair<LL,int>
#define mk make_pair
using namespace std; 
const int N = 5e5 + 3;
LL a[N],sum[N];
inline LL read(){
    char ch = getchar();LL v = 0,c = 1;
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar();    
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar();
    }
    return v * c;    
}
int n,k;int rt[N];
struct Trie{
    struct node{
        int lc,rc;
        int id,size;
    }a[N * 45];
    int t;
    inline void ins(int &u,int id,LL val,int dep){
        a[++t] = a[u];
        u = t;
        a[u].size++;
        if(dep == -1){a[u].id = id;return ;}
        if((1ll << dep) & val) ins(a[u].rc,id,val,dep - 1);
        else ins(a[u].lc,id,val,dep - 1);
    }
    inline pii query(int u1,int u2,LL ans,LL val,int dep){
        if(dep == -1) return mk(ans,a[u2].id);
        int lsum = a[a[u2].lc].size - a[a[u1].lc].size;
        int rsum = a[a[u2].rc].size - a[a[u1].rc].size;
        //printf("%d %d %lld %lld %d %d\n",u1,u2,ans,val,lsum,rsum);
        if((1ll << dep) & val){
            if(lsum) return query(a[u1].lc,a[u2].lc,ans | (1ll << dep),val,dep - 1);
            else return query(a[u1].rc,a[u2].rc,ans,val,dep - 1);
        }
        else{
            if(rsum) return query(a[u1].rc,a[u2].rc,ans | (1ll << dep),val,dep - 1);
            else return query(a[u1].lc,a[u2].lc,ans,val,dep - 1);
        }
    }    
}T;
struct ting{
    LL val;
    int id,from,to,ans_pos;
    ting (int idd,int fromm,int too,int ans_p,LL v){
        id = idd,from = fromm,to = too,ans_pos = ans_p;
        val = v;    
    }
};
bool operator < (const ting &x,const ting &y){
    return x.val < y.val;    
}
priority_queue <ting> q;
int main(){
    n = read(),k = read();
    for(int i = 1;i <= n;++i) a[i] = read(),sum[i] = sum[i - 1] ^ a[i];
//    for(int i = 1;i <= n;++i) printf("%lld\n",sum[i]);puts("");
    T.ins(rt[1],0,sum[0],33);
    for(int i = 1;i < n;++i){
        rt[i + 1] = rt[i];
        T.ins(rt[i + 1],i,sum[i],33);
    }
//    printf("%d\n",rt[0]);
    for(int i = 1;i <= n;++i){
        pii now = T.query(rt[0],rt[i],0,sum[i],33);
    //    printf("%lld %d\n",now.first,now.second);
        q.push(ting(i,0,i - 1,now.second,now.first));
    }
    LL ans = 0;
    while(k--){
        ting now = q.top();q.pop();
        ans += now.val;
    //    printf("%d %d %d %d %lld\n",now.id,now.from,now.to,now.ans_pos,now.val);
        if(now.ans_pos - 1 >= now.from){
            pii cnt = T.query(rt[now.from],rt[now.ans_pos],0,sum[now.id],33);
            q.push(ting(now.id,now.from,now.ans_pos - 1,cnt.second,cnt.first));    
        }
        if(now.ans_pos + 1 <= now.to){
            pii cnt = T.query(rt[now.ans_pos + 1],rt[now.to + 1],0,sum[now.id],33);
            q.push(ting(now.id,now.ans_pos + 1,now.to,cnt.second,cnt.first));    
        }
    }
    printf("%lld\n",ans);
    return 0;    
}
```