<题目链接>
题目大意：
给定一个序列，现在求出两段不相交的区间异或和的最大值。
解题分析：
区间异或问题首先想到01字典树。利用前缀、后缀建树，并且利用异或的性质，相同的两个数异或变成0，从而将前缀操作转化为区间操作，比如：$(a_1 \oplus a_2)\oplus(a_1 \oplus a_2 \oplus a_3 \oplus a_4) = a_3 \oplus a_4$。然后利用简单的$dp$，$predp[i]$记录前$[1~i]$ 任意区间的区间异或最大值(注意不是前缀)，$nxtdp$同理记录后缀区间的最大值。
本题空间卡得比较紧，所以没有另外用一个$val[now]$数组记录Trie树前缀节点所表示的值，而是在$query$中用$ans$代替。
#include <bits/stdc++.h>
using namespace std; const int N = 4e5+;
typedef long long ll;
ll n,pos=,arr[N],nxt[N*][],predp[N],nxtdp[N]; template<typename T>
inline T read(T&x) {
x = ;int f = ; char ch = getchar();
while(ch<'' || ch>'') { if(ch == '-') f=-; ch=getchar(); }
while(ch>='' && ch<='') { x=x*+ch-''; ch=getchar(); }
return x*f;
}
void Insert(ll x){
int now=;
for(int i=;i>=;i--){
int to=(x>>i)&;
if(!nxt[now][to])nxt[now][to]=++pos;
now=nxt[now][to];
}
}
ll query(ll x){
int now=;ll ans=;
for(int i=;i>=;i--){
int to=(x>>i)&;
if(nxt[now][to^])now=nxt[now][to^],ans+=(<<i); //因为最终异或得到的答案就是x中所不包含的数位
else now=nxt[now][to];
}
return ans;
//return x^val[now]; 因为本题空间卡得紧，所以就不能写成这种形式
}
int main(){
read(n);
for(int i=;i<=n;i++)read(arr[i]);
for(int cur=,i=;i<=n;i++){
Insert(cur^=arr[i]);
predp[i]=max(query(cur),predp[i-]); //因为一个数被异或两次等于0，所以这里利用Trie树的前缀操作来实现区间操作
}//得到 i 的前缀区间异或和的最大值
memset(nxt,,sizeof(nxt));
for(int cur=,i=n;i>=;i--){
Insert(cur^=arr[i]);
nxtdp[i]=max(query(cur),nxtdp[i+]);
}//得到 i 的后缀异或区间和的最大值
ll ans=-;
for(int i=;i<=n;i++)ans=max(ans,predp[i]+nxtdp[i]);
printf("%lld\n",ans);
}
2019-03-02