可持久化01trie支持查询最大的区间异或和。

对于普通01trie，我们每次新建的是一条新边（也有可能不建）

而可持久化01trie就像主席树一样，每次利用历史版本新建。

一般学到可持久化01trie的都学过主席树了吧，所以我就不讲思想了

1 struct tree{ 2     LL ch[2],id,cnt; 3 }tr[N*50]; 4 LL tot=0; 5  6 void Insert(LL co,LL &now,LL k,LL pos,LL bit){ 7     // 历史版本，新建的树，数值，原序列中的位置，当前高度  8     tr[now=++tot]=tr[co];//新建节点  9     ++tr[now].cnt;//++次数 10     if(bit<0){tr[now].id=pos;return;}11     bool c=k&(1LL<

 

对于一个起点 i ,找到它与 sum[ (i,n] ] 异或的最大位置，记为pos。

开一个结构体

 

1 struct D{2     LL st;3     LL l,r,pos;//pos可选的区间4     LL sum;//这个可以不用存5     bool operator < (D b) const{6         return sum

压到大根堆里，每次取出最大的，然后把 [ l , r ] 从pos那里分成两个区间，分别算出pos再压进去。

重复k次。

代码写的很仓促，某谷会TLE两个点，仅供参考。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 #define LL long long 9 const int N=500005;10 LL n,x,k;11 LL sum[N];12 struct tree{13 LL ch[2],id,cnt;14 }tr[N*50];15 LL rt[N];16 LL tot=0;17 void Insert(LL co,LL &now,LL k,LL pos,LL bit){18 // 历史版本，新建的树，数值，原序列中的位置，当前高度 19 tr[now=++tot]=tr[co];//新建节点 20 ++tr[now].cnt;//++次数 21 if(bit<0){tr[now].id=pos;return;}22 bool c=k&(1LL<
           
             q;47 48 LL ans=0;49 50 int main(){51 //freopen("1.in","r",stdin);52 scanf("%lld%lld",&n,&k);53 for(LL i=1;i<=n;++i){54 scanf("%lld",&x);55 sum[i]=sum[i-1]^x;56 }57 for(LL i=1;i<=n;++i){58 Insert(rt[i-1],rt[i],sum[i],i,33);59 }60 for(LL i=1;i<=n;++i){61 LL l=i;62 LL r=query(rt[l-1],rt[n],sum[l-1],33);63 q.push((D){l,l,n,r,sum[r]^sum[l-1]});64 }65 while(k--){66 D tmp=q.top();q.pop();67 ans+=tmp.sum;68 LL st=tmp.st;69 LL i=tmp.l,j=tmp.r;70 if(i
            
             tmp.pos){75 LL t=query(rt[tmp.pos],rt[j],sum[st-1],33);76 q.push((D){st,tmp.pos+1,j,t,sum[st-1]^sum[t]});77 }78 }79 cout<