一个非常傻的做法是，枚举区间，使用 ST 表求得次大值并 Trie 算答案。
但是这样真的非常傻……
考虑到每个区间的次大值只有一个，我们可以枚举这个次大值，并找次大值为它的区间。
具体地说，把 \(a_i\) 降序，然后用 set 维护。
不过这个做法是有问题的，比如这组数据： 1
23
12 1 4
输出应该是 \(8\;(12 \oplus 4)\)，但我的代码输出 \(13\;(12 \oplus 1)\)。
不过数据太水了……
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
const int N = 5e4;
const int LG = 30;
int n,a[N + 5],b[N + 5],ans;
set<int> d;
inline bool cmp(int x,int y)
{
return a[x] > a[y];
}
struct node
{
int sum;
int ch[2];
} trie[(N << 7) + 10];
int rt[N + 5];
void insert(int v,int &p)
{
static int tot = 0;
trie[++tot] = trie[p],++trie[p = tot].sum;
int cur = p;
for(register int i = LG;i;--i)
{
trie[++tot] = trie[trie[cur].ch[(v >> i - 1) & 1]],trie[cur].ch[(v >> i - 1) & 1] = tot;
cur = trie[cur].ch[(v >> i - 1) & 1],++trie[cur].sum;
}
}
int query(int v,int p,int q)
{
int ret = 0;
for(register int i = LG;i;--i)
if(trie[trie[q].ch[((v >> i - 1) & 1) ^ 1]].sum - trie[trie[p].ch[((v >> i - 1) & 1) ^ 1]].sum)
ret += 1 << i - 1,p = trie[p].ch[((v >> i - 1) & 1) ^ 1],q = trie[q].ch[((v >> i - 1) & 1) ^ 1];
else
p = trie[p].ch[(v >> i - 1) & 1],q = trie[q].ch[(v >> i - 1) & 1];
return ret;
}
int main()
{
scanf("%d",&n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),b[i] = i,insert(a[i],rt[i] = rt[i - 1]);
sort(b + 1,b + n + 1,cmp);
d.insert(-1),d.insert(0),d.insert(b[1]),d.insert(n + 1),d.insert(n + 2);
for(register int i = 2,l,r;i <= n;d.insert(b[i++]))
{
l = max(1,*----d.lower_bound(b[i]) + 1),r = min(n,*++d.upper_bound(b[i]) - 1);
l <= r && (ans = max(ans,query(a[b[i]],rt[l - 1],rt[r])));
}
printf("%d\n",ans);
}