枚举次小值，找出左右两边第一个、第二个比它大的地方

找的话有两种方法

(1) $O(logn)$

将权值从大到小排序，一个一个加入，用set来维护

(2) $O(log^2n)$

二分位置

用线段树/RMQ来$O(logn)$求出区间最大值

求取区间异或的最大值

可以在可持久化0/1trie上贪心行走

可持久化0/1trie的话

挺简单的，看code吧

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #define mem(a,b) memset(a,b,sizeof(a))#define ll long long#define rint register int#define sum(x) ((x)->sum)using namespace std;inline void read(int &x){ x=0; char q=getchar(); while(q<'0'||q>'9') q=getchar(); while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();}const int N=50006;struct JI{ int pos,v; bool friend operator < (JI a,JI b) { return a.v>b.v; }}ji[N];int l1[N],l2[N],r1[N],r2[N];void out(int vv){ rint i; for(i=31;i>=0;--i) printf("%d",((vv&(1<
             
              >i));}struct trie{ int sum; trie *ch[2]; trie(){sum=0;ch[0]=ch[1]=NULL;}}*root[N],a1[N*33];int n,v[N],size;inline void add(int order){ rint i; int vv=v[order],tt; root[order]=&a1[size++]; trie *pr=root[order-1],*nw=root[order]; for(i=31;i>=0;--i) { tt=((vv&(1<
              
               >i); nw->ch[tt]=&a1[size++]; nw->ch[tt]->sum=pr->ch[tt]->sum+1; nw->ch[tt^1]=pr->ch[tt^1]; nw=nw->ch[tt]; pr=pr->ch[tt]; }}inline int qq(int l,int r,int vv){ if(l>r) return 0; --l; rint i; int tt,ans=0; trie *pr=root[l],*nw=root[r]; for(i=31;i>=0;--i) { //printf("i=%d\n",i); if(nw==NULL||pr==NULL) break; tt=((vv&(1<
               
                >i); if((nw->ch[tt^1]->sum)-(pr->ch[tt^1]->sum)>0) ans|=(1<
                
                 ch[tt^1],pr=pr->ch[tt^1]; else nw=nw->ch[tt],pr=pr->ch[tt]; } //puts(""); //printf("l=%d r=%d\n",l,r); //printf("vv=%d ",vv); out(vv); puts(""); //printf("ans=%d ",ans); out(ans); puts(""); return ans; /*if(l>r) return 0; rint i; int ans=0; for(i=l;i<=r;++i) ans=max(ans,vv^v[i]); return ans;*/}set
                 
                   s;int work(){ rint i,j; /*set
                  
                    :: iterator it; sort(ji+1,ji+1+n); for(i=1;i<=n;++i) { s.insert(ji[i].pos); it=s.find(ji[i].pos); if(it!=s.begin()) { --it; l1[ji[i].pos]=*it; if(it!=s.begin()) { --it; l2[ji[i].pos]=*it; } } it=s.find(ji[i].pos); ++it; if(it!=s.end()) { r1[ji[i].pos]=*it; ++it; if(it!=s.end()) r2[ji[i].pos]=*it; } }*/ for(i=1;i<=n;++i) { l1[i]=i-1; while(v[l1[i]]<=v[i]&&l1[i]>0) --l1[i]; l2[i]=l1[i]-1; while(v[l2[i]]<=v[i]&&l2[i]>0) --l2[i]; if(l2[i]<0) l2[i]=0; r1[i]=i+1; while(v[r1[i]]<=v[i]&&r1[i]<=n) ++r1[i]; r2[i]=r1[i]+1; while(v[r2[i]]<=v[i]&&r2[i]<=n) ++r2[i]; if(r2[i]>n) r2[i]=0; } for(i=1;i<=n;++i) add(i); int ans=0; for(i=1;i<=n;++i) { //printf("i=%d prans=%d ",i,ans); //printf("l2=%d l1=%d r1=%d r2=%d\n",l2,l1,r1,r2); //printf("l2=%d l1=%d r1=%d r2=%d\n",l2[i],l1[i],r1[i],r2[i]); if(!l1[i]) l1[i]=i; if(!r1[i]) r1[i]=i; if(r2[i]) ans=max(ans,qq(l1[i]+1,r2[i]-1,v[i])); if(l2[i]) ans=max(ans,qq(l2[i]+1,r1[i]-1,v[i])); //printf("houans=%d\n",ans); } return ans;}int main(){ freopen("in.in","r",stdin); freopen("alo2.out","w",stdout); rint i,j; root[0]=&a1[size++]; root[0]->ch[0]=root[0]->ch[1]=root[0]; read(n); for(i=1;i<=n;++i) read(ji[i].v),v[i]=ji[i].v,ji[i].pos=i; printf("%d",work());}
                  
                 
                
               
              
             
            
           
          
         
        
       
      

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define mem(a,b) memset(a,b,sizeof(a))#define ll long long#define rint register int#define sum(x) ((x)->sum)using namespace std;inline void read(int &x){ x=0; char q=getchar(); while(q<'0'||q>'9') q=getchar(); while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();}const int N=50006;void out(int vv){ rint i; for(i=31;i>=0;--i) printf("%d",((vv&(1<
            
             >i));}struct trie{ int sum; trie *ch[2]; trie(){sum=0;ch[0]=ch[1]=NULL;}}*root[N],a1[N*33];int n,v[N],size;inline void add(int order){ rint i; int vv=v[order],tt; root[order]=&a1[size++]; trie *pr=root[order-1],*nw=root[order]; for(i=31;i>=0;--i) { tt=((vv&(1<
             
              >i); nw->ch[tt]=&a1[size++]; nw->ch[tt]->sum=pr->ch[tt]->sum+1; nw->ch[tt^1]=pr->ch[tt^1]; nw=nw->ch[tt]; pr=pr->ch[tt]; }}inline int qq(int l,int r,int vv){ if(l>r) return 0; --l; rint i; int tt,ans=0; trie *pr=root[l],*nw=root[r]; for(i=31;i>=0;--i) { //printf("i=%d\n",i); if(nw==NULL||pr==NULL) break; tt=((vv&(1<
              
               >i); if((nw->ch[tt^1]->sum)-(pr->ch[tt^1]->sum)>0) ans|=(1<
               
                ch[tt^1],pr=pr->ch[tt^1]; else nw=nw->ch[tt],pr=pr->ch[tt]; } //puts(""); /*printf("l=%d r=%d\n",l,r); printf("vv=%d ",vv); out(vv); puts(""); printf("ans=%d ",ans); out(ans); puts("");*/ return ans;}int mx[N*5];void build(int l,int r,int x){ if(l==r) { mx[x]=v[l]; return ; } int mid=(l+r)>>1; build(l,mid,x<<1); build(mid+1,r,x<<1|1); mx[x]=(mx[x<<1]>mx[x<<1|1]?mx[x<<1]:mx[x<<1|1]);}void qq(int L,int R,int &ans,int l,int r,int x){ if(L<=l&&r<=R) { if(ans
                
                 >1; if(L<=mid) qq(L,R,ans,l,mid,x<<1); if(mid
                 
                  >1; tt=0; qq(mid,pos,tt,1,n,1); if(tt>vv) ans=mid,l=mid+1; else r=mid-1; } return ans;}int er2(int pos,int vv){ if(pos>n) return 0; int l=pos,r=n,mid,ans=0,tt; while(l<=r) { mid=(l+r)>>1; tt=0; qq(pos,mid,tt,1,n,1); if(tt>vv) ans=mid,r=mid-1; else l=mid+1; } return ans;}int work(){ rint i,j; for(i=1;i<=n;++i) add(i); int ans=0,l1,l2,r1,r2; for(i=1;i<=n;++i) { //printf("i=%d prans=%d ",i,ans); l1=l2=r1=r2=0; l1=er1(i-1,v[i]); r1=er2(i+1,v[i]); l2=er1(l1-1,v[i]); r2=er2(r1+1,v[i]); if(!l1) l1=i; if(!r1) r1=i; //printf("l2=%d l1=%d r1=%d r2=%d ",l2,l1,r1,r2); if(r2) ans=max(ans,qq(l1+1,r2-1,v[i])); if(l2) ans=max(ans,qq(l2+1,r1-1,v[i])); //printf("%d\n",ans); //printf("houans=%d\n",ans); } return ans;}int main(){ //freopen("in.in","r",stdin); //freopen("alo.out","w",stdout); rint i,j; root[0]=&a1[size++]; root[0]->ch[0]=root[0]->ch[1]=root[0]; read(n); for(i=1;i<=n;++i) read(v[i]); build(1,n,1); printf("%d",work());}