#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define N 55000 #define inf 0x3fffffff int ind[N]; int n,a[N]; int b1[N],b2[N]; int qu[N],he; int l[N],r[N]; int tot; int c[N*80][2]; int siz[N*80]; struct P{ int x,y; bool operator<(P a)const{ return y<a.y; } }b[N]; int build(int p,int y,int u){ int x=++tot; siz[x]=siz[p]+1; if(!u)return x; c[x][0]=c[p][0]; c[x][1]=c[p][1]; if((1<<u-1)&y){ c[x][1]=build(c[p][1],y,u-1); }else{ c[x][0]=build(c[p][0],y,u-1); } return x; } int ss; int maxx; int sm[N]; void ask(int L,int R,int y,int u){ if(!u)return; int k=1; if((1<<u-1)&y)k=0; if(siz[c[R][k]]-siz[c[L][k]]){ ss+=(1<<u-1); ask(c[L][k],c[R][k],y,u-1); }else ask(c[L][!k],c[R][!k],y,u-1); } void dele(int x){ if(b1[x])b2[b1[x]]=b2[x]; if(b2[x])b1[b2[x]]=b1[x]; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=(P){i,a[i]}; sort(b+1,b+n+1); for(int i=1;i<=n;i++)b1[i]=i-1,b2[i]=i+1; b2[n]=0; int mi=0; mi=b[n].y; for(int i=1;i<=n;i++){ l[b[i].x]=b1[b1[b[i].x]],r[b[i].x]=b2[b2[b[i].x]]; dele(b[i].x); } for(int i=1;i<=n;i++){ ind[i]=build(ind[i-1],a[i],31); } for(int i=1;i<=n;i++){ if(mi==a[i])continue; if(!r[i])r[i]=n+1; ss=0; ask(ind[l[i]],ind[r[i]-1],a[i],31); maxx=max(maxx,ss); } cout<<maxx; }
bzoj 3166: [Heoi2013]Alo,布布扣,bubuko.com
原文:http://www.cnblogs.com/wangyucheng/p/3714149.html