Description：

给你一个长为 $n$ 的序列，序列中一个长度大于 $1$ 的区间的价值定义为这个区间中的次大值和这个区间中其他任意一个值异或的最大值，求所有区间的价值中的最大值。

$n\le50000$

Solution：

区间次大值的题，想办法找出能是次大值的区间，设比位置 $i$ 上的数大的它前面的第一个位置是 $pre[i]$ ，后面的第一个位置是 $nxt[i]$ ，注意此时可以选的范围不是 $[pre[pre[i]]+1,nxt[i]-1]$ 和 $[pre[i]+1,nxt[nxt[i]]-1]$ ，因为可能这样选不能保证 $i$ 是次大值，应在排序之后向前 $/$ 后找到第二个比它大的数，因为能选的数越多，越有可能更大，所以应让区间尽量大。找出区间之后用可持久化 $trie$ 求区间异或最大值即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cstring>

using namespace std;

int n;

#define MAXN 50010

#define INF 0x3f3f3f3f

int a[MAXN];

struct node

{

	int c[2],cnt;

	node(){c[0] = c[1] = cnt = 0;}

}t[MAXN * 33];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN];

void insert(int &rt,int val,int cur)

{

	int k = newnode();t[k] = t[rt];rt = k;

	if(cur == -1){t[rt].cnt += 1;return;}

	insert(t[rt].c[(val >> cur) & 1],val,cur - 1);

	t[rt].cnt = t[t[rt].c[0]].cnt + t[t[rt].c[1]].cnt;

	return;

}

int query(int r,int l,int val,int cur)

{

	if(cur == -1)return 0;

	int w = ((val >> cur) & 1);

	if(t[t[r].c[w ^ 1]].cnt - t[t[l].c[w ^ 1]].cnt > 0)

		return ((1 << cur) | query(t[r].c[w ^ 1],t[l].c[w ^ 1],val,cur - 1));

	else return query(t[r].c[w],t[l].c[w],val,cur - 1);

}

int pre[MAXN],nxt[MAXN];

int s[MAXN];

bool cmp(int x,int y){return a[x] > a[y];}

int ask(int l,int r,int x)

{

	return query(root[r],root[l - 1],x,31);

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)

	{

		root[i] = root[i - 1];

		insert(root[i],a[i],31);

	}

	for(int i = 1;i <= n;++i)s[i] = i;

	sort(s + 1,s + 1 + n,cmp);

	set<int> ss;

	for(int i = 0;i <= n + 1;++i)pre[i] = 0,nxt[i] = n + 1;

	int ans = 0;

	ss.insert(-1);ss.insert(-2);ss.insert(INF);ss.insert(INF + 1); 

	for(int i = 1;i <= n;++i)

	{

		ss.insert(s[i]);

		set<int>::iterator it = ss.find(s[i]);

		--it;--it;int l = *it;++it;++it;

		++it;++it;int r = *it;

		l = max(1,l);r = min(n,r);

		if(l != r)ans = max(ans,ask(l,r,a[s[i]]));

	}

	cout << ans << endl;

	return 0;

}