题面

Welcome to ALO ( Arithmetic and Logistic Online)。这是一个 VR MMORPG， 如名字所见，到处充满了数学的谜题

现在你拥有 n 颗宝石，每颗宝石有一个能量密度，记为 ai，这些宝石的能量 密度两两不同。现在你可以选取连续的一些宝石（必须多于一个）进行融合，设 为 ai, ai+1, …, aj，则融合而成的宝石的能量密度为这些宝石中能量密度的次大值 与其他任意一颗宝石的能量密度按位异或的值，即，设该段宝石能量密度次大值 为 k，则生成的宝石的能量密度为 max{k xor ap | ap ≠ k , i ≤ p ≤ j}

现在你需要知道你怎么选取需要融合的宝石，才能使生成的宝石能量密度最大

思路

如果知道次大值和区间的话，那蒟蒻桑一定可以做到的吧，呐呐呐。

首先这道题看着很不可做，因为如果爆枚区间并用主席树搞次大值的话那就是$N^2logN$了，显然不可过。让我们来思考一下，首先可持久化$trie$的$log$肯定不能省下，那我们考虑优化这个查找次大值的过程。我们反向思考，不要找区间的次大值，而是找次大值对应的区间。对于每一个点。它作为次大值对应的区间如图所示。

但是有特殊情况，比如向左找不到$L$或者找不到$LL$，向右找不到$R$或者找不到$RR$。

需要自己开动脑筋大力分类讨论，至于怎么找$L$,$LL$,$R$,$RR$的位置🐎，线段树set或者链表并查集什么都可以⑧

代码

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

inline void read(int &x)
{
    int f=1;x=0;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
int n,cnt=1,rt[100005],Max=0;
struct trie{int ls,rs,size;}t[100005*32];
struct seg{int L,R;}tree[4*100005];
struct node{int num,wz;}a[100005];
bool cmp1(node x,node y){return x.num>y.num;}
inline void update(int root)
{
    if (tree[root<<1].L==0) tree[root].L=tree[root<<1|1].L;
    if (tree[root<<1|1].L==0) tree[root].L=tree[root<<1].L;
    if (tree[root<<1].L!=0&&tree[root<<1|1].L!=0) tree[root].L=tree[root<<1|1].L;
    if (tree[root<<1].R==0) tree[root].R=tree[root<<1|1].R;
    if (tree[root<<1|1].R==0) tree[root].R=tree[root<<1].R;
    if (tree[root<<1].R!=0&&tree[root<<1|1].R!=0) tree[root].R=tree[root<<1].R;
}
inline void add(int root,int l,int r,int x)
{
    if (l==r) {tree[root].L=x;tree[root].R=x;return;}
    int mid=l+r>>1;
    if (x<=mid) add(root<<1,l,mid,x);
    else add(root<<1|1,mid+1,r,x);
    update(root);
}
inline int ask_L(int root,int l,int r,int ql,int qr)
{
	if (ql>qr) return 0;
    if (l==ql&&r==qr) return tree[root].L;
    int mid=l+r>>1;
    if (qr<=mid) return ask_L(root<<1,l,mid,ql,qr);
    if (ql>mid) return ask_L(root<<1|1,mid+1,r,ql,qr);
    if (ql<=mid&&qr>mid) return (ask_L(root<<1|1,mid+1,r,mid+1,qr)!=0?ask_L(root<<1|1,mid+1,r,mid+1,qr):ask_L(root<<1,l,mid,ql,mid)); 
}
inline int ask_R(int root,int l,int r,int ql,int qr)
{
	if (ql>qr) return 0;
    if (l==ql&&r==qr) return tree[root].R;
    int mid=l+r>>1;
    if (qr<=mid) return ask_R(root<<1,l,mid,ql,qr);
    if (ql>mid) return ask_R(root<<1|1,mid+1,r,ql,qr);
    if (ql<=mid&&qr>mid) return (ask_R(root<<1,l,mid,ql,mid)!=0?ask_R(root<<1,l,mid,ql,mid):ask_R(root<<1|1,mid+1,r,mid+1,qr)); 
}
inline void insert(int pre,int &root,int i,int x)
{
    root=++cnt;
    t[root]=t[pre];
    t[root].size++;
	if (i<0) return;
    if ((x>>i)&1) insert(t[pre].rs,t[root].rs,i-1,x);
    else insert(t[pre].ls,t[root].ls,i-1,x);
}
inline int query(int pre,int root,int i,int x)
{
    if (i<0) return 0;
    if ((x>>i)&1)
    {
    	if (t[t[root].ls].size-t[t[pre].ls].size>0) return query(t[pre].ls,t[root].ls,i-1,x)+(1<<i);
    	else return query(t[pre].rs,t[root].rs,i-1,x);
	}
    else
    {
    	if (t[t[root].rs].size-t[t[pre].rs].size>0) return query(t[pre].rs,t[root].rs,i-1,x)+(1<<i);
    	else return query(t[pre].ls,t[root].ls,i-1,x);
    }
}
int main()
{
    read(n);
    for (int i=1;i<=n;i++) read(a[i].num),a[i].wz=i,insert(rt[i-1],rt[i],30,a[i].num);
    sort(a+1,a+n+1,cmp1);
    for (int i=1;i<=n;i++) 
    {
		add(1,1,n,a[i].wz);
        if (i==1) continue;
        if (i==2){Max=max(Max,query(rt[0],rt[n],30,a[i].num));continue;}
        int L=ask_L(1,1,n,1,a[i].wz-1),R=ask_R(1,1,n,a[i].wz+1,n);
        int LL=ask_L(1,1,n,1,L-1),RR=ask_R(1,1,n,R+1,n);
        if (LL==0&&L!=0) Max=max(Max,query(rt[0],rt[R-1],30,a[i].num));
        if (RR==0&&R!=0) Max=max(Max,query(rt[L],rt[n],30,a[i].num));
        if (L==0) Max=max(Max,query(rt[0],rt[RR-1],30,a[i].num));
        if (R==0) Max=max(Max,query(rt[LL],rt[n],30,a[i].num));
        if (LL!=0&&R!=0) Max=max(Max,query(rt[LL],rt[R-1],30,a[i].num));
        if (L!=0&&RR!=0)Max=max(Max,query(rt[L],rt[RR-1],30,a[i].num));
    }
    cout<<Max<<endl;
	return 0;
}