处理出每个数最靠近它的左右两个比它大的数。
然后可持久化trie。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 200050 #define inf 1000000007 using namespace std; struct num { int val,id; }p[maxn]; int n,a[maxn]; int seg_ls[maxn<<2],seg_rs[maxn<<2],val1[maxn<<2],val2[maxn<<2],seg_root,seg_tot=0,l1[maxn],l2[maxn],r1[maxn],r2[maxn]; int tree[maxn*50][2],sum[maxn*50],root[maxn],bitt[35],ans=0,tot=0; bool cmp(num x,num y) { return x.val>y.val; } void get_table() { bitt[0]=1; for (int i=1;i<=30;i++) bitt[i]=bitt[i-1]*2; } void build_seg(int &now,int left,int right) { now=++seg_tot;val1[now]=0;val2[now]=inf; if (left==right) return; int mid=(left+right)>>1; build_seg(seg_ls[now],left,mid); build_seg(seg_rs[now],mid+1,right); } int ask_seg(int now,int left,int right,int pos,int type) { if (left==right) { if (type==1) return val1[now]; else return val2[now]; } int mid=(left+right)>>1; if (type==1) { if (pos<=mid) return max(val1[now],ask_seg(seg_ls[now],left,mid,pos,type)); else return max(val1[now],ask_seg(seg_rs[now],mid+1,right,pos,type)); } else { if (pos<=mid) return min(val2[now],ask_seg(seg_ls[now],left,mid,pos,type)); else return min(val2[now],ask_seg(seg_rs[now],mid+1,right,pos,type)); } } void modify_seg(int now,int left,int right,int l,int r,int x,int type) { if ((left==l) && (right==r)) { if (type==1) val1[now]=max(val1[now],x); else val2[now]=min(val2[now],x); return; } int mid=(left+right)>>1; if (r<=mid) modify_seg(seg_ls[now],left,mid,l,r,x,type); else if (l>=mid+1) modify_seg(seg_rs[now],mid+1,right,l,r,x,type); else { modify_seg(seg_ls[now],left,mid,l,mid,x,type); modify_seg(seg_rs[now],mid+1,right,mid+1,r,x,type); } } void work(int x) { l1[p[x].id]=ask_seg(seg_root,1,n,p[x].id,1); if (l1[p[x].id]==0) l2[p[x].id]=0; else { if (l1[p[x].id]==1) l2[p[x].id]=0; else l2[p[x].id]=ask_seg(seg_root,1,n,l1[p[x].id]-1,1); } r1[p[x].id]=ask_seg(seg_root,1,n,p[x].id,2); if (r1[p[x].id]==inf) {r1[p[x].id]=n+1;r2[p[x].id]=n+1;} else { if (r1[p[x].id]==n) r2[p[x].id]=n+1; else r2[p[x].id]=ask_seg(seg_root,1,n,r1[p[x].id]+1,2); if (r2[p[x].id]==inf) r2[p[x].id]=n+1; } modify_seg(seg_root,1,n,p[x].id,n,p[x].id,1); modify_seg(seg_root,1,n,1,p[x].id,p[x].id,2); } void insert(int b,int last,int &now,int x) { now=++tot; tree[now][0]=tree[last][0];tree[now][1]=tree[last][1]; sum[now]=sum[last]+1; if (b==-1) return; int tmp=x&bitt[b];tmp>>=b; insert(b-1,tree[last][tmp],tree[now][tmp],x); } int ask(int b,int last,int now,int x) { if (b==-1) return 0; int tmp=x&bitt[b];tmp>>=b; int r=sum[tree[now][tmp^1]]-sum[tree[last][tmp^1]]; if (r>0) return ask(b-1,tree[last][tmp^1],tree[now][tmp^1],x)+bitt[b]; else return ask(b-1,tree[last][tmp],tree[now][tmp],x); } int main() { get_table(); scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); p[i].val=a[i];p[i].id=i; } sort(p+1,p+n+1,cmp); build_seg(seg_root,1,n); for (int i=1;i<=n;i++) work(i); for (int i=1;i<=n;i++) insert(30,root[i-1],root[i],a[i]); for (int i=1;i<=n;i++) { int l,r; l=l2[i]+1;r=r1[i]-1; ans=max(ans,ask(30,root[l-1],root[r],a[i])); l=l1[i]+1;r=r2[i]-1; ans=max(ans,ask(30,root[l-1],root[r],a[i])); } printf("%d ",ans); return 0; }