做前缀异或和，用堆维护一个五元组(x,l,r,p,v)，x为区间右端点的值，l~r为区间左端点的范围，p为x在l~r中最大异或和的位置，v为该最大异或和，每次从堆中取出v最大的元素，以p为界将其切成两部分重新扔进堆即可。查询一个值在一个区间中的最大异或和用可持久化trie实现。luogu上T掉了。

#include
     
       #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define ll long long#define N 500010#define ui unsigned intchar 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<
            
             0],x,i-1,ID);}struct data2{ ui x;int l,r,p;ui d; bool operator <(const data2&a) const { return d
             
               q;int query(int l,int r,ui x){ for (int i=31;~i;i--) { int op=(x&(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\n";#else const char LL[]="%lld\n";#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
              
             
            
           
          
         
        
       
      
     

　　场上写的是CF1055F的做法（当然没有隐式建trie了）。考场代码：

#include
     
      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
      
        pii;typedef pair
       
         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<
        
         0]) trie[k][(x&(I<
         
          0]=++cnt;        k=trie[k][(x&(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<