3226. 【HBOI2013】ALO

Description

Welcome to ALO ( Arithmetic and Logistic Online)。這是一個VR MMORPG，如名字所見，到處充滿了數學的謎題。

現在你擁有n顆寶石，每顆寶石有一個能量密度，記為ai，這些寶石的能量密度兩兩不同。現在你可以選取連續的一些寶石（必須多于一個）進行融合，設為ai, ai+1, …, aj，則融合而成的寶石的能量密度為這些寶石中能量密度的次大值與其他任意一顆寶石的能量密度按位異或的值的最大值，即，設該段寶石能量密度次大值為k，則生成的寶石的能量密度為max{k xor ap | ap ≠ k , i ≤ p ≤ j}。

現在你需要知道你怎麼選取需要融合的寶石，才能使生成的寶石能量密度最大。

Input

第一行，一個整數n，表示寶石個數。

第二行，n個整數，分别表示a1至an，表示每顆寶石的能量密度，保證對于i ≠ j有ai ≠ aj。

Output

輸出一行一個整數，表示最大能生成的寶石能量密度。

Sample Input

5

9 2 1 4 7      

Sample Output

14      

Data Constraint

對于20%的資料有n ≤ 100。

對于50%的資料有n ≤ 2000。

對于100%的資料有1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9。

Hint

樣例解釋：選擇區間[1,5]，最大值為7 xor 9。

Solution

考試時想出來了可持久化Trie，但是沒有想到如何求離目前點最近的比目前點大的第二個位置。

首先枚舉次大值。

預處理出次大值前面的第一個比它大的位置（記為l[ i ]），第二個比它大的位置（記為L[ i ]）。

以及後面第一個比它大的位置（記為r[ i ]），第二個比它大的位置（記為R[ i ]）。

那麼答案即為區間（l[ i ]+1~R[ i ]-1）以及（L[ i ]+1~r[ i ]-1）的最大值。

建立一棵可持久化Trie，對于區間直接詢問異或最大值即可。

假設我們已經求出來了l[]和r[]，

那麼對于每個位置記錄fir[x]表示它後面第一個l[fir[x]]=x即比x小的離x最近的l[]等于x的點。（設為y）

那麼每次從x-1往前跳l指針，知道找到一個比y大的點，那麼L[y]=x。同時y不斷跳r[y]并保證a[y]<a[x]

對于R[y]同理。

時間複雜度最多為log

總時間複雜度O(n log n)。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(register I i=a;i<=b;i++)
#define Fd(i,a,b) for(register I i=a;i>=b;i--)
#define N 50002
using namespace std;
I n,a[N],l[N],r[N],L[N],R[N],s[N],fir[N],las[N],tp,cnt,A[N],tr[N*31][2],bz[N*31],rt[N],tot,ans;
struct node{I v,id;}o[N];
I cmp(node x,node y){return x.v<y.v;}
void ins(I x,I y,I s){
	Fd(i,29,0){
		bz[x]=bz[y]+1;
		if((s>>i)&1){
			if(!tr[x][1]) tr[x][1]=++tot;
			tr[x][0]=tr[y][0],x=tr[x][1],y=tr[y][1];
		}
		else{
			if(!tr[x][0]) tr[x][0]=++tot;
			tr[x][1]=tr[y][1],x=tr[x][0],y=tr[y][0];
		}
	}
	bz[x]=bz[y]+1;
}
I qry(I x,I y,I s){
	I sum=0,k;
	Fd(i,29,0){
		k=(s>>i)&1;
		if(bz[tr[y][!k]]-bz[tr[x][!k]]){sum+=1<<i;y=tr[y][!k],x=tr[x][!k];}
		else{x=tr[x][k],y=tr[y][k];}
	}
	return sum;
}
I main(){
	freopen("ALO.in","r",stdin);
	freopen("ALO.out","w",stdout);
	scanf("%d",&n);
	F(i,1,n){
		scanf("%d",&a[i]);
		ins(rt[i]=++tot,rt[i-1],a[i]);
		o[i]=node{a[i],i};
	}
	sort(o+1,o+1+n,cmp);
	F(i,1,n){A[o[i].id]=(cnt+=(o[i].v!=o[i-1].v));}
	F(i,1,n){
		while(tp&&a[s[tp]]<a[i]) tp--;
		l[i]=s[tp];
		if(!fir[l[s[++tp]=i]]) fir[l[i]]=i;
	}
	s[tp=0]=n+1;
	Fd(i,n,1){
		while(tp&&a[s[tp]]<a[i]) tp--;
		r[i]=s[tp];
		if(!las[r[s[++tp]=i]])  las[r[i]]=i;
	}
	/*F(i,1,n){
		Fd(j,l[i]-1,1) if(a[j]>a[i]){
			L[i]=j;break;
		}
		R[i]=n+1;
		F(j,r[i]+1,n) if(a[j]>a[i]){
			R[i]=j;break;
		}
	}*/
	F(i,1,n) if(fir[i]){
		for(register I j=fir[i],k=i-1;k&&j<=n&&l[j]==i;j=r[j]){
			while(k&&a[k]<a[j]) k=l[k];
			if(k) L[j]=k;else break;
		}
		/*x=i-1,y=fir[i];
		while(y<=n){
			if(l[y]!=i) break;
			while(x&&a[x]<a[y]) x=l[x];
			if(!x) break;
			L[y]=x,y=r[y];
		}*/
	}
	Fd(i,n,1) if(las[i]){
		for(register I j=las[i],k=i+1;k&&j&&r[j]==i;j=l[j]){
			while(k<=n&&a[k]<a[j]) k=r[k];
			if(k<=n) R[j]=k;else break;
		}
		/*I x=i+1,y=las[i];
		while(y){
			if(r[y]!=i) break;
			while(x<=n&&a[x]<a[y]) x=r[x];
			if(x>n) break;
			R[y]=x,y=l[y];
		}*/
	}
	F(i,1,n){
		if(r[i]) ans=max(ans,qry(rt[L[i]],rt[r[i]-1],a[i]));
		if(R[i]) ans=max(ans,qry(rt[l[i]],rt[R[i]-1],a[i]));
	}
	printf("%d\n",ans);
	return 0;
}