传送门
01trie经典题目。
我们可以通过计算每个数作为次小值时对答案的贡献。
显然对于每个iii需要求出一个包含a[i]a[i]a[i]且的区间[l,r][l,r][l,r]且区间所有值都小于a[i]a[i]a[i]
于是将原数组排序之后用双向链表维护。
接着用01trie贪心求出贡献。
#include<bits/stdc++.h>
#define N 200005
#define P 30
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,rt[N],pre[N],nt[N],ans=0;
struct node{int id,val;}a[N];
inline bool cmp(node a,node b){return a.val<b.val;}
struct Trie{
int son[N*30][2],siz[N*30],tot;
inline int insert(int las,int val){
int p,ret;
p=ret=++tot;
for(int i=P;~i;--i){
son[p][0]=son[las][0],son[p][1]=son[las][1],siz[p]=siz[las]+1;
int tmp=(val>>i)&1;
son[p][tmp]=++tot,las=son[las][tmp],p=son[p][tmp];
}
siz[p]=siz[las]+1;
return ret;
}
inline int query(int l,int r,int val){
int ret=0;
for(int i=P;~i;--i){
int tmp=(val>>i)&1;
if(siz[son[r][tmp^1]]-siz[son[l][tmp^1]])ret|=(1<<i),l=son[l][tmp^1],r=son[r][tmp^1];
else l=son[l][tmp],r=son[r][tmp];
}
return ret;
}
}T;
int main(){
n=read();
for(int i=1;i<=n;++i)a[i]=(node){i,read()},pre[i]=i-1,nt[i]=i+1,rt[i]=T.insert(rt[i-1],a[i].val);
pre[0]=0,nt[0]=1,pre[n+1]=n,nt[n+1]=n+1,sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i){
int tmp=a[i].id,lasl=pre[tmp],lasr=nt[tmp],l=pre[lasl],r=nt[lasr];
if(l+1<=lasr-1)ans=max(ans,T.query(rt[l],rt[lasr-1],a[i].val));
if(r-1>=lasl+1)ans=max(ans,T.query(rt[lasl],rt[r-1],a[i].val));
nt[pre[tmp]]=nt[tmp],pre[nt[tmp]]=pre[tmp];
}
printf("%d",ans);
return 0;
}