本文主要是介绍#trie#洛谷 4098 JZOJ 3226 ALO，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
分析
首先肯定会想到建一棵可持久化01trie，但是关键是次大值，所以考虑从小到大排序，那么每次该数都会有一段选择的区间，那么考虑把它合并给左右，用该值当次大值在trie中找到区间中最大的一个，其实这道题实际操作比理论还要难，至少我是这么认为的
代码
#include <cstdio>
#include <cctype>
#include <deque>
#include <algorithm>
#define rr register
using namespace std;
const int INF=2e9+11,N=50011; pair<int,int>b[N];
int l[N],r[N],a[N],n,cnt,root[N],ans;
inline signed iut(){rr int ans=0; rr char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;
}
struct I_AC_the_Task{int son[N*31],tr[N*31][2],tot;inline void Insert(int x){rr int rt=root[cnt];root[++cnt]=++tot;for (rr int i=29;~i;--i){rr int p=(x>>i)&1;son[tot]=son[rt]+1;tr[tot][p]=tot+1;tr[tot][p^1]=tr[rt][p^1];rt=tr[rt][p],++tot;}son[tot]=son[rt]+1;}inline signed query(int l,int r,int x){rr int ls=root[l],rs=root[r],ans=0;for (rr int i=29;~i;--i){rr int p=(x>>i)&1;if (son[tr[ls][p^1]]<son[tr[rs][p^1]])ls=tr[ls][p^1],rs=tr[rs][p^1],ans|=1<<i;else ls=tr[ls][p],rs=tr[rs][p]; }return ans;}
}trie;
inline signed max(int a,int b){return a>b?a:b;}
signed main(){n=iut(); a[0]=a[n+1]=INF; r[0]=1,l[n+1]=n; trie.tot=0;for (rr int i=1;i<=n;++i) a[i]=iut(),l[i]=i-1,r[i]=i+1;for (rr int i=1;i<=n;++i) b[i]=make_pair(a[i],i),trie.Insert(a[i]);sort(b+1,b+1+n);for (rr int i=1;i<=n;++i){rr int pos=b[i].second,L=l[pos],R=r[pos]; l[R]=L,r[L]=R;if (L>=1) ans=max(ans,trie.query(l[L],R-1,a[pos]));if (R<=n) ans=max(ans,trie.query(L,r[R]-1,a[pos]));}return !printf("%d",ans);
} 这篇关于#trie#洛谷 4098 JZOJ 3226 ALO的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
