# bzoj 3166 [Heoi2013]Alo

### Description

Welcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG ，

5

9 2 1 4 7

14

【样例解释】

### 题解

#include <cstdio>
#include <set>
#include <algorithm>
#include <cstring>
#define N 50010
#define inf 0x3f3f3f3f
using namespace std;
set<int>se;
struct data{int v,id;}a[N];
bool comp(data a,data b){return a.v>b.v;}
int val[N*40],ch[N*40][2],sz,root[N*40],n,ans;
void insert(int &now,int x,int dep)
{
val[++sz]=val[now]+1,ch[sz][0]=ch[now][0],
ch[sz][1]=ch[now][1],now=sz;
if (dep==-1) return;
insert(ch[now][1&(x>>dep)],x,dep-1);
}
int query(int l,int r,int x,int dep)
{
if (dep==-1) return 0;
if (val[ch[r][(1&(x>>dep))^1]]-val[ch[l][(1&(x>>dep))^1]]>0)
return (query(ch[l][(1&(x>>dep))^1],ch[r][(1&(x>>dep))^1],x,dep-1)|(1<<dep));
else
return query(ch[l][1&(x>>dep)],ch[r][1&(x>>dep)],x,dep-1);
}
main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i].v),a[i].id=i;
for (int i=1;i<=n;i++)
root[i]=root[i-1],insert(root[i],a[i].v,31);
sort(a+1,a+1+n,comp);
se.insert(-1);se.insert(inf);se.insert(-2);se.insert(inf+1);
se.insert(a[1].id);
for(int i=2;i<=n;i++)
{
int l=a[i].id,r=a[i].id,x=a[i].id;
set<int>::iterator s1,s2;
s1=s2=se.lower_bound(x);
r=*s1;s1++;r=*s1-1;
l=*--s2;s2--;l=*s2+1;
l=max(1,l);r=min(r,n);
if(l!=r)
ans=max(ans,query(root[l-1],root[r],a[i].v,31));
se.insert(x);
}
printf("%d",ans);
}