P4098 题解

· · 题解

对于每一个数，我们先考虑它可以和哪些数异或。

令 L_i 为第 i 个数左边第一个比它大的数的下标，R_i 为第 i 个数右边第一个比它大的数的下标。

设当前这个数为 i，那么以它为次大值的区间有 \left[ L_{L_i}+1,R_i -1 \right] 和 \left[ L_i+1,R_{R_i} -1\right]。

那么如何找出来我们要的 L 和 R 呢？ 考虑用链表连接整个区间，从小到大的查找每一个数的 L 和 R，也就是 前驱 和 后驱，并在结束时将当前的点丢出链表。因为排序，所以这样处理的复杂度是 O(n\log n) 的。

对于每一个区间，我们可以把所有的 a 放进一颗字典树上，然后在字典树上查找所有的 a 与 a_i 异或的最大值。

因为区间始终是在 \left[ 1,n \right] 里面的，所以可以考虑可持久化，于是每次查询的复杂度就降成了 O(\log n)。

代码


#include<bits/stdc++.h>
using namespace std;

int n,m,ans=0;;
int a[6000005],tot=0;
int root[20000005];

struct Trie{
    int t[80000005][2],cnt=0;
    int sum[80000005];
    void Change_Tree(int l,int &r,int val){
        r=++cnt,sum[r]=sum[l]+1;
        int x=l,y=r;
        for(int i=30;i>=0;i--){
            int op=((val>>i)&1);
            t[y][!op]=t[x][!op];
            t[y][op]=++cnt,sum[t[y][op]]=sum[t[x][op]]+1;
            x=t[x][op],y=t[y][op];
        }
    }
    int Find_Tree(int x,int y,int val){
//      printf("Fuck:%d %d %d\n",x,y,val);
        if(x>y) return 0;
        int ans=0;
        for(int i=30;i>=0;i--){
            int op=((val>>i)&1);
            if(sum[t[y][!op]]-sum[t[x][!op]]>0) ans+=(1<<i),op=(!op);
            x=t[x][op],y=t[y][op];
        }
        return ans;
    }
}T;

int lsh[500005];
int val[500005];
int pre[500005],nxt[500005];
int ll[500005],rr[500005];

struct qwq{
    int val,id;
}t[500005];
bool cmp(qwq x,qwq y){
    return x.val<y.val;
}
int L[500005],R[500005];

void Print(){
    printf("-----------------------------\n");
    for(int i=1;i<=n;i++) printf("%d:%d %d\n",i,pre[i],nxt[i]);
    printf("-----------------------------\n");
}

int main(){
    cin>>n;for(int i=1;i<=n;i++) scanf("%d",&a[i]),t[i].val=a[i],t[i].id=i,pre[i]=i-1,nxt[i]=i+1,T.Change_Tree(root[i-1],root[i],a[i]);
    pre[n+1]=n,nxt[0]=1;
    sort(t+1,t+n+1,cmp);
    for(int i=1;i<=n;i++){
        int id=t[i].id;
        L[id]=pre[id],R[id]=nxt[id];
        pre[R[id]]=L[id],nxt[L[id]]=R[id];
        ll[id]=pre[L[id]],rr[id]=nxt[R[id]];
//      printf("%d:%d %d %d %d\n",id,L[id],R[id],ll[id],rr[id]); 
//      Print();
    }
    for(int i=1;i<=n;i++){
        int l=L[i],r=R[i];
        int pr=ll[i],nx=rr[i];
//      printf("%d:%d %d %d %d %d\n",i,l,r,pr,nx,a[i]);
        if(l) ans=max(ans,T.Find_Tree(root[pr],root[r-1],a[i]));//,printf("qwq!\n");
        if(r!=n+1) ans=max(ans,T.Find_Tree(root[l],root[nx-1],a[i]));//,printf("QWQ!\n");
    }
    printf("%d\n",ans);
    return 0;
}