题解 P4098 【[HEOI2013]ALO 】

· · 题解

其实是个好题

首先我们考虑枚举区间，肯定不能直接枚举左右边界，因为那样会严重超时
我们考虑枚举次小值k的位置，然后借助双向链表求出它可能对应的两个区间，即先按照权值从小到大排序，然后依次在链表中获取它的前驱和后继，即对应的区间，然后将该节点在链表里删除（感觉描述不清楚，看楼上）
然后即使求区间最大异或和（很熟悉对不对？），没错，就是这道题最大异或和，我们借助可持久化trie即可求出最后的答案 

#include<bits/stdc++.h>
using namespace std;
int n,a[50005],prev[50005],next[50005],root[50005],top=0;
int l[200005],r[200005],to[200005],trie[200005*32][2],latest[5000005];
struct sor{
    int data;
    int where;
}s[50005];
bool cmp(sor x,sor y){
    return x.data<y.data;
}
void insert(int val,int i,int now,int com,int F){
    if(F<0){
        latest[now]=i;return;
    }
    int x=val&(1<<(F))?1:0;
    trie[now][x^1]=trie[com][x^1];
    trie[now][x]=++top;
    insert(val,i,trie[now][x],trie[com][x],F-1);
    latest[now]=max(latest[trie[now][0]],latest[trie[now][1]]);
}
int ask(int Min,int now,int val,int F){
    if(F<0)return latest[now];
    int x=val&(1<<(F))?1:0;
    if(latest[trie[now][x^1]]>=Min)return ask(Min,trie[now][x^1],val,F-1);
    else return ask(Min,trie[now][x],val,F-1);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),prev[i]=i-1,next[i]=i+1,
        s[i].data=a[i],s[i].where=i;
    sort(s+1,s+n+1,cmp);int tot=0;
    for(int i=1;i<=n;i++){
        int x=s[i].where;
        if(prev[x]){
            l[++tot]=prev[prev[x]]+1;
            r[tot]=next[x]-1;to[tot]=x;
        }
        if(next[x]<=n){
            l[++tot]=prev[x]+1;
            r[tot]=next[next[x]]-1;to[tot]=x;
        }
        next[prev[x]]=next[x];
        prev[next[x]]=prev[x];
    }
    latest[0]=-1;root[0]=++top;
    insert(0,0,top,0,31);
    for(int i=1;i<=n;i++)
      root[i]=++top,insert(a[i],i,root[i],root[i-1],31);
    int ans=0;
    for(int i=1;i<=tot;i++){
        //cout<<l[i]<<" "<<r[i]<<" "<<to[i]<<endl;
        ans=max(ans,a[ask(l[i],root[r[i]],a[to[i]],31)]^a[to[i]]);
    }
    printf("%d\n",ans);
    return 0;
}