输入数据的第一行包含一个整数N，表示数组中的元素个数。
第二行包含N个整数A1,A2,…,AN。
输出一行包含给定表达式可能的最大值。
5
1 2 3 1 2
6
满足条件的(l1,r1,l2,r2)有：(1,2,3,3)，(1,2,4,5)，(3,3,4,5)。
对于100%的数据，2 ≤ N ≤ 4*105，0 ≤ Ai ≤ 109。
这道题,似乎也是套路题啊,只不过多了那么一点点思路。
考虑几点:
于是我们考虑用 01字典树 来求解。
我们可以很方便地处理出在一段区间内最大异或和的区间。
直接记录一遍异或前缀和,然后一个一个插入并查询即可。
但是由于不能选相交的区间,我们不能考虑直接选两个最大的区间。
可以考虑用一个数组:
\[f[maxn]\]
用于储存前 ( 1 , i ) 区间的异或最大值。
那么我们记录完之后,直接从后面再开始一遍选最大区间。
我们从 n枚举到 1;
\[Ans=\max_{i=1}^n(Ans,f[i-1]+query(sub[i]))\]
其中sub 数组表示 n 到 i 异或后缀和。
如以上求解即可,时间复杂度 O(2*nlogn)。
不过这题需要注意以下空间不能开太大。
#include<bits/stdc++.h>
using namespace std;
const int maxn=400008;
int c[maxn],f[maxn];
int n,m,pre[maxn],sub[maxn];
int ch[32*maxn][2];
int val[32*maxn];
int num[32*maxn];
int sz,ans=-1;
void init()
{
memset(ch[0],0,sizeof(ch[0]));
sz=1;
}
void insert(int a)
{
int u=0;
for(int i=32;i>=0;i--)
{
int c=((a>>i)&1);
if(!ch[u][c])
{
memset(ch[sz],0,sizeof(ch[sz]));
val[sz]=0;
num[sz]=0;
ch[u][c]=sz++;
}
u=ch[u][c];
num[u]++;
}
val[u]=a;
return;
}
int query(int x)
{
int u=0;
for(int i=32;i>=0;i--)
{
int c=((x>>i)&1);
if(ch[u][c^1]&&num[ch[u][c^1]])
u=ch[u][c^1];
else u=ch[u][c];
}
return x^val[u];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&c[i]);
for(int i=1;i<=n;i++)
pre[i]=pre[i-1]^c[i];
for(int i=n;i>0;i--)
sub[i]=sub[i+1]^c[i];
for(int i=1;i<=n;i++)
f[i]=max(f[i-1],query(pre[i])),
insert(pre[i]);
init(); insert(sub[n+1]);
for(int i=n;i>0;i--)
ans=max(ans,query(sub[i])+f[i-1]),
insert(sub[i]);
cout<<ans<<endl;
return 0;
} [BZOJ4260] Codechef REBXOR (01字典树,异或前缀和)
原文：https://www.cnblogs.com/Kv-Stalin/p/9244841.html