.jpg)
Solution:
01trie树求异或和最大。
先正反都求一遍异或前缀和，每次都将当前的前缀和加入01tire树中，同时查询并更新$ln[i]$和$rn[i]$（分别表示$[1,i]$的最大连续异或和，$[i,n]$的最大连续异或和），那么答案$ans=max(ln[i]+rn[i+1])$，注意的细节是trie树要清0并在tire树中先插入一个0以便保证第一次插入的异或前缀和是其本身。
代码：
1 #include<bits/stdc++.h> 2 #define il inline 3 #define ll long long 4 #define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++) 5 #define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--) 6 using namespace std; 7 const int N=4e5+7; 8 int trie[N*31][2],cnt,n,a[N],sum,ln[N],rn[N],ans; 9 10 il void insert(int a){ 11 int x,p=0; 12 Bor(i,0,31){ 13 x=(1<<i)&a?1:0; 14 if(!trie[p][x])trie[p][x]=++cnt; 15 p=trie[p][x]; 16 } 17 } 18 19 il int search(int a){ 20 int x,p=0,ans=0; 21 Bor(i,0,31){ 22 x=(1<<i)&a?0:1; 23 if(trie[p][x])ans+=1<<i,p=trie[p][x]; 24 else p=trie[p][x^1]; 25 if(!p)return ans; 26 } 27 return ans; 28 } 29 30 il void init(){ 31 scanf("%d",&n); 32 For(i,1,n) scanf("%d",&a[i]); 33 sum=0,insert(0); 34 For(i,1,n) sum^=a[i],insert(sum),ln[i]=max(search(sum),ln[i-1]); 35 sum=0; 36 memset(trie,0,sizeof(trie)),cnt=0,insert(0); 37 Bor(i,1,n) sum^=a[i],insert(sum),rn[i]=max(search(sum),rn[i+1]); 38 For(i,1,n) ans=max(ln[i]+rn[i+1],ans); 39 cout<<ans; 40 } 41 42 int main(){ 43 init(); 44 return 0; 45 }
原文：https://www.cnblogs.com/five20/p/9477953.html