3166: [Heoi2013]Alo

这题大意是给你一个序列，求一个最优区间[l,r],使其中的次大值xor上区间中任意另一个数，使xor和最大（对不起，我又语死了）

这题其实暴力能a= =

但是写暴力太没节操了（- -b）

网上似乎没有除暴力以外的题解= =我来写一篇吧= =

我的大致想法就是用线段树维护i前面第二个比他大的值f[i]（这里可以用权值线段树），然后用函数式trie找(f[i]+1,i)上与a[i]的最大xor。。

貌似很基础的样子= =也很暴力= =

有更优解请告诉我= =

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3000010;
struct re{
	int l,r,lc,rc,ms,mf;
} t[N];
int root[N],col[N],a[N],b[N],c[N],d[N];
int tr[N][2];
int n,sum=0,num=0,tot=0,ans=0;
inline void inse(int pp,int i,int x){
	root[i]=++sum;
	int pos=root[i];
	col[pos]=i;
	for (int j=30;j>=0;j--){
		int y=(x>>j)&1;
		tr[pos][y^1]=tr[pp][y^1];
		tr[pos][y]=++sum;
		col[sum]=i;
		pos=tr[pos][y];
		pp=tr[pp][y];
	}
}
inline int ques(int l,int r,int x){
	int pos=root[r];
	int ans=0;
	for (int j=30;j>=0;j--){
		int z=(x>>j)&1;
		if (col[tr[pos][z^1]]>=l){
			ans+=1<<j;
			pos=tr[pos][z^1];
		}else pos=tr[pos][z];
	}
	return ans;
}
inline int buildtree(int l,int r){
	int x=++num;
	t[x].l=l;
	t[x].r=r;
	t[x].mf=t[x].ms=0;
	if (l==r){
		t[x].lc=t[x].rc=0;
		return x;
	}
	int mm=(l+r)/2;
	t[x].lc=buildtree(l,mm);
	t[x].rc=buildtree(mm+1,r);
	return x;
}
inline void renew(int c,int x){
	if (t[x].mf<c){
		t[x].ms=t[x].mf;
		t[x].mf=c;
		return;
	}
	if (t[x].mf==c) return;
	if (t[x].ms<c) t[x].ms=c;
}
inline void down(int x){
	int l=t[x].lc,r=t[x].rc;
	renew(t[x].ms,l);
	renew(t[x].mf,l);
	renew(t[x].ms,r);
	renew(t[x].mf,r);
}
inline int query(int x,int pos){
	if (t[x].l==t[x].r) return t[x].ms;
	down(x);
	int mm=(t[x].l+t[x].r)/2;
	if (pos<=mm) return query(t[x].lc,pos);
	return query(t[x].rc,pos);
}
inline void add(int x,int l,int r,int c){
	if (t[x].l==0) return;
	if (l<=t[x].l&&t[x].r<=r){
		t[x].ms=t[x].mf;
		t[x].mf=c;
		return;
	}
	down(x);
	int mm=(t[x].l+t[x].r)/2;
	if (l<=mm) add(t[x].lc,l,r,c);
	if (mm<r) add(t[x].rc,l,r,c);
}
inline void calc(){
	memset(col,0,sizeof(col));
	memset(tr,0,sizeof(tr));
	sum=0; tot=0;
	inse(0,0,0);
	for (int i=1;i<=n;i++){
		b[++tot]=a[i];
		inse(root[i-1],i,a[i]);
	}
	std::sort(b+1,b+n+1);
	for (int i=1;i<=n;i++){
		c[i]=lower_bound(b+1,b+n+1,a[i])-b;
	}
	num=0;
	int ro=buildtree(1,n);
	for (int i=1;i<=n;i++){
		int x;
		x=query(ro,c[i]);
		x++;
		ans=max(ans,ques(x,i,a[i]));
		if (c[i]>1) add(ro,1,c[i]-1,i);
	}
}
inline void read(int &T){
	int ch=getchar();
	while (ch<'0'||ch>'9'){
		ch=getchar();
	}
	T=0;
	while (ch>='0'&&ch<='9'){
		T=T*10+ch-'0';
		ch=getchar();
	}
}
int main(){
	scanf("%d",&n);
	num=0;
	for (int i=1;i<=n;i++){
		scanf("%d",&d[i]);
		a[i]=d[i];
	}
	calc();
	for (int i=1;i<=n;i++) a[i]=d[n-i+1];
	calc();
	printf("%d\n",ans);
}