与区间某数得异或最大值很简单 用01trie即可
麻烦得是维护次小值所管辖得范围
将次小值从大到小排列 并将其原来得下表插入set 所以左端点就是前驱的前驱+1 右端点就是后继的后继-1
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=2e6+10; int n,T[N],lson[N],siz[N],rson[N],t[N][2],ncnt; void upnode(int k,int val,int pre,int &pos) { pos=++ncnt; siz[pos]=siz[pre]+1; t[pos][0]=t[pre][0]; t[pos][1]=t[pre][1]; if(k<0)return ; int c=(val>>k)&1; upnode(k-1,val,t[pre][c],t[pos][c]); } int qmax(int k,int val,int pre,int pos) { if(k<0)return 0; int c=(val>>k)&1; int x=siz[t[pos][c^1]]-siz[t[pre][c^1]]; if(x)return (1<<k)+qmax(k-1,val,t[pre][c^1],t[pos][c^1]); else return qmax(k-1,val,t[pre][c],t[pos][c]); } set<int>s; int a[N],b[N]; bool cmp(int x,int y){return a[x]>a[y];} int main() { scanf("%d",&n); rep(i,1,n)scanf("%d",&a[i]),upnode(30,a[i],T[i-1],T[i]),b[i]=i; sort(b+1,b+1+n,cmp); s.insert(b[1]);s.insert(-1);s.insert(-2);s.insert(n+1);s.insert(n+2); int ans=0; rep(i,2,n) { int l=max(1,*(--(--s.upper_bound(b[i])))+1); int r=min(*(++s.upper_bound(b[i]))-1,n); if(l>r)continue; s.insert(b[i]); ans=max(ans,qmax(30,a[b[i]],T[l-1],T[r])); } cout<<ans; return 0; }