题意：给出n个数字（n<=1e6），求出一段区间[ l , r ]使得这段区间数字的抑或和最大。如果有多个最大区间，输出字典序最小的一个。
题解：枚举区间右端点 r ，那么左端点 l 一定比 r 小，同时[ l , r ]的抑或和可以表示成 [ 1, r ]xor[ 1 , l-1 ]，那么我们枚举一个 r，求出[ 1, r]的和，然后就是查询[1, 1 ][ 1, 2 ] [1 , 3 ]……[1, r-1]中和[1,r]抑或最大的那个值。这个可以通过01字典树完成，然后还要求字典序最小，字典树终点处记一个l位置，然后更新就行了。
PS：数组模拟字典树
Code：
#include<stdio.h> #include<cstring> #include<algorithm> using namespace std; const int MAX = 1e6+100; int bas[35]; const int INF = 2147483645; struct Trie{ int nxt[MAX<<2][2]; int l[MAX<<2]; int cnt; int ansl,ansr,ansv; void init(){ cnt =0; memset(nxt[0],0,sizeof (nxt[0])); memset(l,0x3f3f3f3f,sizeof(l)); ansv = 0; } int create(){ cnt++; memset(nxt[cnt],0,sizeof (nxt[cnt])); return cnt; } void insert(int id,int x){ int y = 0; for (int i=30;i>=0;i--){ int t = x&bas[i]; t>>=i; if (!nxt[y][t]){ nxt[y][t] = create(); } y = nxt[y][t]; } l[y] = min(l[y],id); } void query(int id,int x){ int y=0; int res =0; for (int i=30;i>=0;i--){ int t = x&bas[i]; t>>=i; // cout<<t<<" "<<nxt[y][!t]<<endl; if (nxt[y][!t]){ y =nxt[y][!t]; res+=bas[i]; }else{ y = nxt[y][t]; } } // cout<<"Query: "<<l[y]<<" "<<id<<" "<<x<<" "<<res<<" "<<ansv<<endl; if (res==ansv){ if (l[y]<ansl){ ansl = l[y]; ansr = id; } }else if (res>ansv){ ansv = res; ansl = l[y]; ansr = id; } } void print(int id){ printf("Case #%d:\n%d %d\n",id,ansl+1,ansr); } }trie; void init(){ bas[0] = 1; for (int i=1;i<=30;i++){ bas[i] = bas[i-1]<<1; } } int main(){ init(); int n,Cas; scanf("%d",&Cas); for (int i=1;i<=Cas;i++){ trie.init(); trie.insert(0,0); scanf("%d",&n); int sum=0; for (int j=1;j<=n;j++){ int ai; scanf("%d",&ai); sum^=ai; trie.query(j,sum); trie.insert(j,sum); } trie.print(i); } return 0; }