Description
Input
输入数据的第一行包含一个整数N，表示数组中的元素个数。
第二行包含N个整数A1,A2,…,AN。
Output
输出一行包含给定表达式可能的最大值。
Sample Input
5 1 2 3 1 2
Sample Output
6
HINT
满足条件的(l1,r1,l2,r2)有：(1,2,3,3)，(1,2,4,5)，(3,3,4,5)。
对于100%的数据，2 ≤ N ≤ 4*105，0 ≤ Ai ≤ 109。
Source
题解
自己trie树感觉不太会，练一练（都要NOIP考试了还在学0.0）
其实很多xor的问题都是trie树（记得机房外面还有写着trie树——解决xor问题）
那么这道题我们要怎么做呢？
我们用b[i]表示从左到右，以i为结尾的最大异或和
同理，另一个式子我们也可以这么做
1 #include2 #define N 400005 3 using namespace std; 4 int n,cnt,len,Max; 5 int p[31]; 6 int a[N],s[N],M[N]; 7 struct node{ 8 int l,r,val; 9 }tr[31*N];10 void get(int x){11 len=0;12 while (x){13 p[++len]=x%2;14 x>>=1;15 }16 }17 void insert(int x){18 int y=1;19 for (int i=31;i>len;i--){20 if (!tr[y].l) tr[y].l=++cnt; 21 y=tr[y].l;22 }23 for (int i=len;i>=1;i--)24 if (p[i]){25 if (!tr[y].r) tr[y].r=++cnt;26 y=tr[y].r;27 } else{28 if (!tr[y].l) tr[y].l=++cnt ;29 y=tr[y].l;30 }31 tr[y].val=x;32 }33 int find(int x){34 int y=1;35 for (int i=31;i>len;i--)36 y=tr[y].r?tr[y].r:tr[y].l;37 for (int i=len;i>=1;i--)38 if (p[i])39 y=tr[y].l?tr[y].l:tr[y].r;40 else41 y=tr[y].r?tr[y].r:tr[y].l;42 return tr[y].val;43 }44 int main(){45 scanf("%d",&n);46 for (int i=1;i<=n;i++)47 scanf("%d",&a[i]);48 int ans;49 cnt=1;50 for (int i=1;i<=n;i++){51 s[i]=s[i-1]^a[i];52 get(s[i]);53 ans=s[i]^find(s[i]);54 M[i]=max(M[i-1],ans);55 insert(s[i]);56 }57 memset(tr,0,sizeof(tr));58 memset(s,0,sizeof(s));59 cnt=1;60 for (int i=n;i>=1;i--){61 s[i]=s[i+1]^a[i];62 get(s[i]);63 ans=(s[i]^find(s[i]))+M[i-1];64 if (ans>Max) Max=ans;65 insert(s[i]);66 }67 printf("%d\n",Max);68 return 0;69 }