10051. 「一本通 2.3 例 3」Nikitosh 和异或

求A序列中的两个子序列（ L1<=R1 < L2<=R2）,使  XORS( 1 ) +XORS( 2 )最大

XORS(区间内整数的异或和）

 求 left[i] ,right[i] 前缀和后缀的 区间内最大异或和  ,dp ：left[ i] =max( left[i-1] ,v)

v 是考虑以i 结尾的区间的贡献， 求一个j ，使XOR( j , i ) 最大，用前缀和思想 （ pre[i] = a[1] ^ a[2] ^ a[3] ....a[i] )

 v= pre[j] ^ pre[i]

#include<iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 const int N=4e5+2;
 int ch[N*32][2],tot;
 int n;
 int a[N],g[N],f[N];
 void insert(int x){
     int i,c,u=1;
     
     for(i=31;i>=0;i--){
          c=(x>>i)&1;
         if(ch[u][c]==0){
             ch[u][c]=++tot; 
         }
         u=ch[u][c];
     }
 }
 int find(int x){
     int i,c,u=1;
     int res=0;
     for(i=31;i>=0;i--){
         c= (x>>i)&1; c=c^1;
         
         if(ch[u][c]) res+=(1<<i),u=ch[u][c];
         else u=ch[u][c^1];
     }
     return res;
 }
 main(){
     int i,t;
     cin>>n ; 
     tot=1; t=0;
     for(i=1;i<=n;i++){
         cin>>a[i];
         t^=a[i]; insert(t);
         f[i]=max(f[i-1],find(t));
     }
     memset(ch,0,sizeof ch);
     tot=1; t=0;
     for(i=1;i<=n;i++){
         t^=a[i]; insert(t);
         find(t); g[i]=max(g[i+1],find(t));
     }
     
     int ans=0;
    for(i=1;i<=n;i++){
        ans=max(ans,f[i]+g[i+1]);
    }
    cout<<ans;
 }