题意分析

题目链接

这里借鉴了\(Youngsc\)以及\(hzwer\)的思路

首先由于涉及到了区间异或最值的问题

所以我们需要使用到\(01Trie\)树

这里贴一道板子题

然后对一个位置\(x\)

我们维护四个位置\(l_1,l_2,r_1,r_2\)

\(l_1\) 从\(x\)往左数第一个大于\(x\)的位置

\(l_2\) 从\(x\)往左数第二个大于\(x\)的位置

\(r_1\) 从\(x\)往右数第一个大于\(x\)的位置

\(r_2\) 从\(x\)往右数第二个大于\(x\)的位置

那么\(x\)作为次大值的区间就是\([l_1+1,r_2-1]\)以及\([l_2+1,r_1-1]\)

至于维护这四个位置 我们使用\(set\)就可以了

把位置按照权值从大到小排序

然后依次插入 就可以了

CODE:

/*-------------OI使我快乐-------------*/
int n,tot,cnt,ans;
struct Node{
    int val,pos;
    friend bool operator < (const Node &A,const Node &B)
    {return A.val>B.val;}
}num[M];
set<int> key;
int root[M],siz[M*31],tre[M*31][2];
IL void insert(int cdy,int &wzy,int val)
{
    int tmp;tmp=wzy=++tot;
    for(R int i=30;i>=0;--i)
    {
        tre[tmp][0]=tre[cdy][0];tre[tmp][1]=tre[cdy][1];
        siz[tmp]=siz[cdy]+1;
        int nxt=((val&(1<<i))>>i);
        cdy=tre[cdy][nxt];
        tre[tmp][nxt]=++tot;
        tmp=tre[tmp][nxt];
    }
    siz[tmp]=siz[cdy]+1;
}
IL int qury(int cdy,int wzy,int val)
{
    int tmp=0;
    for(R int i=30;i>=0;--i)
    {
        int nxt=((val&(1<<i))>>i);
        if(siz[tre[wzy][nxt^1]]-siz[tre[cdy][nxt^1]])
        tmp+=(1<<i),wzy=tre[wzy][nxt^1],cdy=tre[cdy][nxt^1];
        else wzy=tre[wzy][nxt],cdy=tre[cdy][nxt];
    }
    return tmp;
}
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n);
    for(R int i=1;i<=n;++i) read(num[i].val),num[i].pos=i;
    for(R int i=1;i<=n;++i) insert(root[i-1],root[i],num[i].val);
    key.insert(-inf);key.insert(-inf+1);key.insert(inf);key.insert(inf-1);//哨兵元素
    sort(num+1,num+n+1);
    key.insert(num[1].pos);
    for(R int i=2;i<=n;++i)
    {
//      printf("now at %d\n",num[i].pos);
        int le,ri;
        set<int>::iterator cdy,wzy,zjz,ghj;
//最后位置的分布是 zjz,cdy,wzy,ghj      zjz=key.lower_bound(num[i].pos);ghj=zjz;
        wzy=(ghj++);cdy=(--zjz);--zjz;
        if((*cdy)>0)
        {
            le=max(1,(*zjz)+1);ri=min(n,*wzy-1);
//          printf("case1 %d %d\n",le,ri);
            ans=max(ans,qury(root[le-1],root[ri],num[i].val));  
        }
        if((*wzy)<=n)
        {
            le=max(1,(*cdy)+1);ri=min(n,*ghj-1);
//          printf("case2 %d %d\n",le,ri);
            ans=max(ans,qury(root[le-1],root[ri],num[i].val));          
        }
        key.insert(num[i].pos);
    }
    printf("%d\n",ans);
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

HEOI 2019 RP++

P4098 [HEOI2013]ALO

原文：https://www.cnblogs.com/LovToLZX/p/10616752.html