然而原题打不开……
水一道 提高+/省选− 和一道 省选/NOI−。
题意分析
如果是只求一个区间，那么问题就会十分简单。
因为异或满足结合律，因此可以构造序列 $a$ 的前缀异或和，然后和最大异或对一样 $\mathcal O\left(n\log n\right)$ 使用01Trie求解。
然而这里有两个区间。
我们不能先求最大值，然后再求分裂出的两个区间的最大值——因为可能存在两个更小的值，但是和大于这种情况。
我们考虑将原区间拆分为两个区间求解。
这样，在两个区间内分别求解一次，然后合并答案取最大值即可。
但是这样听起来时间复杂度似乎是 $\mathcal O\left(n^2\log n\right)$，无法通过此题：枚举分割线 $\mathcal O(n)$，求解 $\mathcal O\left(n\log n\right)$。
我们可以定义前缀数组 $pre$ 和后缀数组 $suf$，$pre_i$ 表示 $[1,i]$ 中最大的区间异或和，$suf_i$ 表示 $[i,n]$ 中最大的异或和。
而 $pre,suf$ 都能够在 $\mathcal O\left(n\log n\right)$ 的时间内预处理出来。
不过需要注意的一点就是，递推求解之前需要往 01Trie 中先插入一个 $0$，这表示从 $1$（或 $n$）开始选取。
AC 代码
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=4e5;
//pre[i]:1~i的最大异或和,suf[i]:i~n的最大异或和
int n,a[N+1],b[N+1],pre[N+1],suf[N+1];
struct trie{//01Trie
struct node{
int m[2];
}t[32*N+1];
int top;
void clear(){
top=0;
memset(t,0,sizeof(t));
}
void insert(int x){
int p=0;
for(int i=31;i>=0;i--){
int bit=x>>i&1;
if(!t[p].m[bit]){
t[p].m[bit] = ++top;
}
p=t[p].m[bit];
}
}
int query(int x){
int p=0,ans=0;
for(int i=31;i>=0;i--){
int bit=x>>i&1;
if(t[p].m[!bit]){
ans|=(!bit)<<i;
p=t[p].m[!bit];
}else{
ans|=bit<<i;
p=t[p].m[bit];
}
}return ans;
}
}t;
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
}
for(int i=n;i>=1;i--){
b[i]=b[i+1]^a[i];//构造后缀异或和
}
for(int i=1;i<=n;i++){
a[i]^=a[i-1];//构造前缀异或和
}
pre[1]=a[1];
t.insert(0);
t.insert(a[1]);
for(int i=2;i<=n;i++){
pre[i]=max(pre[i-1],a[i]^t.query(a[i]));
t.insert(a[i]);
}
t.clear();//注意清空
suf[n]=b[n];
t.insert(0);
t.insert(b[n]);
for(int i=n-1;i>=1;i--){
suf[i]=max(suf[i+1],b[i]^t.query(b[i]));
t.insert(b[i]);
}
int ans=0;
for(int i=1;i<n;i++){
ans=max(ans,pre[i]+suf[i+1]);
}printf("%d\n",ans);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
