Lightoj1269
本题的题意是求出一段连续的区间，使这段区间异或和最小/最大。分别输出最大异或值和最小异或值。
区间异或和的题目一般都要用到前缀异或和，我们这里可以预处理出前缀异或和，然后我们考虑，对于每个值，在字典树上查找之前出现过的最优的匹配，利用字典树的特点，将其拆为二进制，贪心的去查找，查找最大值则是0找1，1找0，查找最小值则是1找1，0找0。维护一下最大值与最小值即可。Find的时候可以利用两个不同的root并行查找最大值与最小值，减少代码量。
Lightoj1269代码
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
const int maxn =3e6+5;
int tree[maxn][2];
int tot;
int ans,ans2;
int flagg[maxn];
void insert_(int num)
{int root=0;int pos=30;int id;while(pos!=-1){if(num&(1<<pos)) id=1;else id=0;if(!tree[root][id]) tree[root][id]=++tot;root=tree[root][id];pos--;}return ;
}
void find_(int num)
{int root=0;int root2=0;int pos=30;int id;ans=0;ans2=0;while(pos!=-1){if(num&(1<<pos)) id=1;else id=0;if(tree[root][id^1])//最大值优先找相反的0-1，1-0{ans^=(1<<pos);root=tree[root][id^1];}else{root=tree[root][id];}if(tree[root2][id])//最小值优先找相同的0-0，1-1{root2=tree[root2][id];}else{ans2^=(1<<pos);root2=tree[root2][id^1];}pos--;}
}
int a[maxn];
int sum[maxn];
int main()
{int n,t;int cnt=1;scanf("%d",&t);while(t--){tot=0;int maxx=0;int minn=0x3f3f3f3f;scanf("%d",&n);insert_(0);for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i]=a[i]^sum[i-1];find_(sum[i]);//先查找minn=min(ans2,minn);maxx=max(ans,maxx);insert_(sum[i]);//后插入，避免本身造成影响}printf("Case %d: %d %d\n",cnt++,maxx,minn);for(int i=0;i<=tot;i++){tree[i][0]=0;tree[i][1]=0;}}return 0;
}