题目大意：
有一个长度为n的序列，求1≤l1≤r1<l2≤r2≤n使得(⊕r1i=l1ai)+(⊕r2i=l2ai)最大，输出这个最大值。
思路：
用Trie求出前缀异或和以及后缀异或和，再求出前缀异或和以及后缀异或和中最大的，前后相加，求最大值。用可持久化Trie求异或和也可（较慢）。
代码：
Trie：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #define M 400009 5 using namespace std; 6 int cnt,ans,child[M<<5][2],a[M],lmax[M],rmax[M]; 7 8 void build(int x) 9 { 10 int i,w,now=0; 11 for (i=1<<30;i;i>>=1) 12 { 13 w=(x&i)?1:0; 14 if (!child[now][w]) child[now][w]=++cnt; 15 now=child[now][w]; 16 } 17 } 18 19 int cal(int x) 20 { 21 int i,w,now=0,ans=0; 22 for (i=1<<30;i;i>>=1) 23 { 24 w=(x&i)?0:1; 25 if (child[now][w]) ans+=i,now=child[now][w]; 26 else now=child[now][!w]; 27 } 28 return ans; 29 } 30 31 int main() 32 { 33 int n,i,now; scanf("%d",&n); 34 for (i=1;i<=n;i++) scanf("%d",&a[i]); 35 for (build(now=0),i=1;i<=n;i++) 36 { 37 build(now^=a[i]); 38 lmax[i]=max(cal(now),lmax[i-1]); 39 } 40 memset(child,0,sizeof(child)); 41 for (build(now=cnt=0),i=n;i;i--) 42 { 43 build(now^=a[i]); 44 rmax[i]=max(cal(now),rmax[i+1]); 45 } 46 for (i=0;i<=n;i++) ans=max(ans,lmax[i]+rmax[i+1]); 47 printf("%d\n",ans); 48 return 0; 49 }可持久化Trie：
1 #include<cstdio> 2 #include<iostream> 3 #define M 400009 4 using namespace std; 5 6 int sum[M<<5],lc[M<<5],rc[M<<5],a[M],root[M<<5],cnt; 7 8 int read() 9 { 10 int x=0; 11 char ch=getchar(); 12 while (ch<'0' || ch>'9') ch=getchar(); 13 while (ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar(); 14 return x; 15 } 16 17 void build(int &cur,int _cur,int x,int k) 18 { 19 sum[cur=++cnt]=sum[_cur]+1;if (k<0) return; 20 if (x&(1<<k)) lc[cur]=lc[_cur],build(rc[cur],rc[_cur],x,k-1); 21 else rc[cur]=rc[_cur],build(lc[cur],lc[_cur],x,k-1); 22 } 23 24 int ask(int x,int y,int val) 25 { 26 int i,ans=0; 27 for (i=30;i>=0;i--) 28 if (val&(1<<i)) 29 if (sum[lc[y]]-sum[lc[x]]) ans|=1<<i,x=lc[x],y=lc[y]; 30 else x=rc[x],y=rc[y]; 31 else if (sum[rc[y]]-sum[rc[x]]) ans|=1<<i,x=rc[x],y=rc[y]; 32 else x=lc[x] ,y=lc[y]; 33 return ans; 34 } 35 36 int main() 37 { 38 int n=read(),i,mx=0,ans=0; 39 for (i=1;i<=n;i++) a[i]=read()^a[i-1]; 40 for (i=1;i<=n;i++) build(root[i],root[i-1],a[i],30); 41 for (i=n-1;i;i--) 42 { 43 mx=max(mx,ask(root[i],root[n],a[i])); 44 ans=max(ans,mx+ask(root[1],root[i],a[i])); 45 } 46 printf("%d",ans); 47 return 0; 48 }
转载于:https://www.cnblogs.com/HHshy/p/5754294.html
