非常类似那道超级钢琴
维护一个可持久化01trie即可
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=2e6+10; int T[N],t[N<<5][2],ncnt,siz[N<<5]; void upnode(int k,ll val,int v,int pre,int &pos) { pos=++ncnt; t[pos][0]=t[pre][0]; t[pos][1]=t[pre][1]; siz[pos]=siz[pre]+v; if(k==-1)return ; if( (val>>k)&1 )upnode(k-1,val,v,t[pre][1],t[pos][1]); else upnode(k-1,val,v,t[pre][0],t[pos][0]); } ll qmax(int k,ll val,int pos) { if(k==-1)return 0; int c=(val>>k)&1; if(siz[t[pos][c^1]])return qmax(k-1,val,t[pos][c^1])+(1<<k); else return qmax(k-1,val,t[pos][c]); } struct node{ll v;int x;}; bool operator< (node a,node b){return a.v<b.v;} priority_queue<node>q; ll a[N],ans;int n,k; int main() { scanf("%d%d",&n,&k); rep(i,1,n) { ll x;scanf("%lld",&x);a[i]=a[i-1]^x; } //upnode(32,0,1,T[0],T[0]); rep(i,1,n)upnode(32,a[i-1],1,T[i-1],T[i]); rep(i,1,n)q.push((node){qmax(32,a[i],T[i]),i}); while(k--) { node u=q.top();q.pop(); ans+=u.v; upnode(32,u.v^a[u.x],-1,T[u.x],T[u.x]); q.push((node){qmax(32,a[u.x],T[u.x]),u.x}); } cout<<ans; return 0; }