做前缀异或和，用堆维护一个五元组(x,l,r,p,v)，x为区间右端点的值，l~r为区间左端点的范围，p为x在l~r中最大异或和的位置，v为该最大异或和，每次从堆中取出v最大的元素，以p为界将其切成两部分重新扔进堆即可。查询一个值在一个区间中的最大异或和用可持久化trie实现。luogu上T掉了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
#define N 500010
#define ui unsigned int
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
ui read()
{
ui x=0;char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
int n,k,goat,root[N],cnt;
const ui I=1;
ui a[N];
struct data{int ch[2],s,id;
}trie[N*33];
void ins(int &k,ui x,int i,int ID)
{
trie[++cnt]=trie[k];k=cnt;
trie[k].s++;trie[k].id=ID;
if (i<0) return;
ins(trie[k].ch[(x&(I<<i))>0],x,i-1,ID);
}
struct data2
{
ui x;int l,r,p;ui d;
bool operator <(const data2&a) const
{
return d<a.d;
}
};
priority_queue<data2> q;
int query(int l,int r,ui x)
{
for (int i=31;~i;i--)
{
int op=(x&(I<<i))>0;
if (trie[trie[r].ch[op^1]].s>trie[trie[l].ch[op^1]].s) l=trie[l].ch[op^1],r=trie[r].ch[op^1];
else l=trie[l].ch[op],r=trie[r].ch[op];
}
return trie[r].id;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
const char LL[]="%I64d
";
#else
const char LL[]="%lld
";
#endif
cin>>n>>k;ins(root[0],0,31,0);
for (int i=1;i<=n;i++)
{
root[i]=root[i-1];
a[i]=a[i-1]^read();
ins(root[i],a[i],31,i);
}
root[-1]=0;
for (int i=1;i<=n;i++)
{
int p=query(root[-1],root[i-1],a[i]);
q.push((data2){a[i],0,i-1,p,a[i]^a[p]});
}
ll ans=0;
while (k--)
{
data2 t=q.top();q.pop();ans+=t.d;int x=t.p;
if (x>t.l)
{
int p=query(root[t.l-1],root[x-1],t.x);
q.push((data2){t.x,t.l,x-1,p,t.x^a[p]});
}
if (x<t.r)
{
int p=query(root[x],root[t.r],t.x);
q.push((data2){t.x,x+1,t.r,p,t.x^a[p]});
}
}
cout<<ans;
return 0;
}
场上写的是CF1055F的做法（当然没有隐式建trie了）。考场代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 500010
#define uint unsigned int
#define mp(x,y) make_pair((x),(y))
uint read()
{
uint x=0;char c=getchar();
while (c<'0'||c>'9') c=getchar();
while (c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
return x;
}
typedef pair<int,int> pii;
typedef pair<uint,int> pui;
int n,k,trie[N*33][2],size[N*33],nxt[N*33],head[N*33],T,cnt;
pii p[N*4],q[N*4];
uint val[N*33],a[N],v[N*33];
pui b[N*4];
ll ans;
void ins(uint x)
{
int k=0;uint I=1;
for (int i=31;~i;i--)
{
if (!trie[k][(x&(I<<i))>0]) trie[k][(x&(I<<i))>0]=++cnt;
k=trie[k][(x&(I<<i))>0];size[k]++;
v[++T]=x;nxt[T]=head[k];head[k]=T;
}
val[k]=x;
}
bool cmp(pui a,pui b)
{
return a.first>b.first;
}
int main()
{
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
n=read(),k=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<=n;i++) a[i]^=a[i-1];
for (int i=0;i<=n;i++) ins(a[i]);
cnt=1;p[1]=mp(0,0);
for (int _=32;_;_--)
{
ll tot=0;
for (int i=1;i<=cnt;i++)
{
tot+=1ll*size[trie[p[i].first][0]]*size[trie[p[i].second][1]];
if (p[i].first!=p[i].second) tot+=1ll*size[trie[p[i].first][1]]*size[trie[p[i].second][0]];
}
if (tot>k)
{
int u=0;
for (int i=1;i<=cnt;i++)
{
if (p[i].first!=p[i].second&&(trie[p[i].first][0]>0&&trie[p[i].second][1]>0))
{
q[++u].first=trie[p[i].first][0];
q[u].second=trie[p[i].second][1];
}
if (trie[p[i].first][1]>0&&trie[p[i].second][0]>0)
{
q[++u].first=trie[p[i].first][1];
q[u].second=trie[p[i].second][0];
}
}
cnt=u;for (int i=1;i<=cnt;i++) p[i]=q[i];
}
else
{
k-=tot;
for (int i=1;i<=cnt;i++)
{
int L=trie[p[i].first][0],R=trie[p[i].second][1];
for (int x=head[L];x;x=nxt[x])
for (int y=head[R];y;y=nxt[y])
ans+=v[x]^v[y];
if (p[i].first!=p[i].second)
{
int L=trie[p[i].first][1],R=trie[p[i].second][0];
for (int x=head[L];x;x=nxt[x])
for (int y=head[R];y;y=nxt[y])
ans+=v[x]^v[y];
}
}
int u=0;
for (int i=1;i<=cnt;i++)
{
if (trie[p[i].first][0]>0&&trie[p[i].second][0]>0)
{
q[++u].first=trie[p[i].first][0];
q[u].second=trie[p[i].second][0];
}
if (trie[p[i].first][1]>0&&trie[p[i].second][1]>0)
{
q[++u].first=trie[p[i].first][1];
q[u].second=trie[p[i].second][1];
}
}
cnt=u;for (int i=1;i<=cnt;i++) p[i]=q[i];
}
}
for (int i=1;i<=cnt;i++)
{
b[i].first=val[p[i].first]^val[p[i].second];
if (1ll*size[p[i].first]*size[p[i].second]>k) b[i].second=k;
else b[i].second=size[p[i].first]*size[p[i].second];
}
sort(b+1,b+cnt+1,cmp);
for (int i=1;i<=cnt;i++)
if (k>b[i].second) ans+=1ll*b[i].first*b[i].second,k-=b[i].second;
else {ans+=1ll*b[i].first*k;break;}
cout<<ans;
return 0;
}