题目：
http://www.wzoi.org/usaco/16%5C107.asp
总的来说就是给定一个数列(n<=100000)。
求一段连续的子数列，使得其中的数都xor在一起以后，得到的值最大。
分析：
自己想的原创算法吖
首先我们先分析一下xor这个运算的性质。
易得y=y xor t xor t（即偶数次xor同一个数，结果和原来一样）
于是我们可以设s[i]表示从a[1]xor到a[i]的值。(定义s[0]=0)
如果我们需要某一段[i,j]的xor值，就可以这样求s[j] xor s[i-1]，因为a[1]到a[i-1]的数被xor了两次！
这样，问题转化为：求max(s[i] xor s[j])，其中i∈[0,j]，j∈[1,n]。
于是现在要求的是取两个数的xor值最大！
首先我们应该明白，对于一个数字，我们可以把它看成一个长度为20的字符串(题目给的a[i]<=2^21-1)！
那么我们怎么比较这些字符串的大小呢？
很明显，我们是从首位扫到末尾！
于是假设我们现在枚举j，即已经确定了s[j]，然后在[0,j]的范围类找一个s[i] xor s[j]最大。
因为是当成字符串，我们用Trie树来储存那些数字！
然后从首位开始：
1、如果我这个s[j]的这一位是0，那么另外一个配对最好是1，
因为这样xor会得到1。如果找不到那就只能到0那边去。
2、如果我这个s[j]的这一位是1，那么另外一个配对最好是0，
理由同上。
因为越前的位在大小上影响更大，所以我们这样就贪心的走一遍Trie树，
所得的结果就是和s[j]配对最大的s[i]。
然后统计每个j对应的最大值，输出结果即可。
HINT
UASCO给的空间比较小，用指针可以过，但静态空间的Trie就不能开到极限那么大，开小一点就能过。
code：
/*
ID:jie22221
TASK:cowxor
LANG:C++
*/
#include
struct treetype{int l,r,dep;}T[5*N];
struct gtp{int x,y,next;}g[N];
int n,a[N],s[N],ans=-1,ansi=0,ansj=0,tot,root,e=0,ls[5*N];
void addedge(int x,int y){
e++;
g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}
void add(int &p,int x,int dep,int link){
if (p==0){
tot++;
p=tot;
T[p].l=0;
T[p].r=0;
T[p].dep=dep;
}
if (dep==-1){
addedge(p,link);
return;
}
if (((1<
}
void init(){
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<=n;i++){
s[i]=s[i-1]^a[i];
if (a[i]>ans){
ans=a[i];
ansi=i;
ansj=i;
}
if (s[i]>ans){
ans=s[i];
ansi=1;
ansj=i;
}
}
tot=1;
root=1;
T[1].l=0;
T[1].r=0;
T[1].dep=22;
}
inline bool flag(int x,int y,int z){
if (x>ans) return true;
if (x
if (z-y
}
void work(){
add(root,s[1],22,1);
for (int i=2;i<=n;i++){
int p=root,now=0;
for (int j=22;j>=0;j–)
if ((s[i]|(1<
}
else {
if (T[p].r!=0) {p=T[p].r; now|=1<
}
if (flag(now,g[ls[p]].y+1,i)){
ans=now;
ansi=g[ls[p]].y+1;
ansj=i;
}
add(root,s[i],22,i);
}
}
void print(){
printf("%d %d %dn",ans,ansi,ansj);
}
int main(){
freopen("cowxor.in","r",stdin);
freopen("cowxor.out","w",stdout);
init();
work();
print();
return 0;
}