[HEOI2013]ALO（可持久化Trie+链表）

你永远不会相信一个快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=;

int n,cnt,ans,a[N],rt[N],ch[N*][],sz[N*],L[N],R[N];

pii b[N];

void build(int x,int id)

{

    int u,v=rt[id-];u=rt[id]=++cnt;

    sz[u]=sz[v]+;

    for(int i=;~i;i--)

    {

        int c=x>>i&;

        ch[u][c^]=ch[v][c^],ch[u][c]=++cnt;

        u=ch[u][c],v=ch[v][c],sz[u]=sz[v]+;

    }

}

int query(int x,int l,int r)

{

    if(l>r)return ;

    l=rt[l-],r=rt[r];

    int ret=;

    for(int i=;~i;i--)

    {

        int c=x>>i&;

        if(sz[ch[r][c^]]-sz[ch[l][c^]])ret+=<<i,l=ch[l][c^],r=ch[r][c^];

        else l=ch[l][c],r=ch[r][c];

    }

    return ret;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&a[i]),build(a[i],i),b[i]=pii(a[i],i),L[i]=i-,R[i]=i+;

    sort(b+,b+n+);

    for(int i=;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]+,r-));

        if(r)ans=max(ans,query(a[x],l+,R[r]-));

    }

    printf("%d",ans);

}