你永远不会相信一个快AFO的选手不会可持久化Trie。
其实异或粽子那题可以用可持久化Trie做，不过我还是没用，用的一般的Trie（其实可持久化是多此一举），于是到现在还是不会可持久化Trie。
这题首先可以发现要求的是最大值，所以很多区间是没必要的，l1[i]/r1[i]表示左/右边第1个比a[i]大的数，l2[i]/r2[i]表示左/右边第2个比a[i]大的数，然后询问的区间显然是[l2[i]+1,r1[i]-1]和[l1[i]+1,r2[i]-1]二者的最大值，然后由于询问的是连续段的异或最大值，可以发现就是可持久化Trie的板子了，至于l[i],r[i]，用链表式维护即可，不需要set/treap等大常数做法。
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>pii; const int N=50005; int n,cnt,ans,a[N],rt[N],ch[N*32][2],sz[N*32],L[N],R[N]; pii b[N]; void build(int x,int id) { int u,v=rt[id-1];u=rt[id]=++cnt; sz[u]=sz[v]+1; for(int i=29;~i;i--) { int c=x>>i&1; ch[u][c^1]=ch[v][c^1],ch[u][c]=++cnt; u=ch[u][c],v=ch[v][c],sz[u]=sz[v]+1; } } int query(int x,int l,int r) { if(l>r)return 0; l=rt[l-1],r=rt[r]; int ret=0; for(int i=29;~i;i--) { int c=x>>i&1; if(sz[ch[r][c^1]]-sz[ch[l][c^1]])ret+=1<<i,l=ch[l][c^1],r=ch[r][c^1]; else l=ch[l][c],r=ch[r][c]; } return ret; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]),build(a[i],i),b[i]=pii(a[i],i),L[i]=i-1,R[i]=i+1; sort(b+1,b+n+1); for(int i=1;i<=n;i++) { int x=b[i].second,l=L[x],r=R[x];L[r]=l,R[l]=r; if(l)ans=max(ans,query(a[x],L[l]+1,r-1)); if(r)ans=max(ans,query(a[x],l+1,R[r]-1)); } printf("%d",ans); }
原文：https://www.cnblogs.com/hfctf0210/p/10991674.html
