题意
分析
将区间异或和转化为前缀异或和.那么[L,R][L,R][L,R]的异或和就等于presum[R] xor presum[L−1]presum[R]\ xor \ presum[L-1]presum[R] xor presum[L−1].所以相当于求presum[l1] xor presum[r1] + presum[l2] xor presum[r2]presum[l1]\ xor \ presum[r1]\ +\ presum[l2]\ xor \ presum[r2]presum[l1] xor presum[r1] + presum[l2] xor presum[r2]的最大值.这里0≤l1<r1≤l2<r2≤N0\le l1<r1\le l2<r2\le N0≤l1<r1≤l2<r2≤N.那么我们只要算出前缀两两异或最大值和后缀两两异或最大值,枚举每一个位置,然后把lmx[i]+rmx[i+1]lmx[i]+rmx[i+1]lmx[i]+rmx[i+1]取最大值就得到了答案.那怎么求这个前后缀两两异或最大值呢?拿lmxlmxlmx举例,有lmx[i]=Max{ lmx[i−1], Max0≤j<i{presum[i] xor presum[j]} }lmx[i]=Max\{\ lmx[i-1], \ {Max}_{0\le j<i}\{presum[i]\ xor\ presum[j]\}\ \}lmx[i]=Max{ lmx[i−1], Max0≤j<i{presum[i] xor presum[j]} }求presum[i]presum[i]presum[i]异或上前面所有的值得到的最大值可以用0-1trie树来做.考虑贪心的策略.首先一定要让最高位尽量为1,那么就在trie树上跑,如果当前值xxx在这一位上位1,那么就优先往0那边走,如果xxx当前值为0,那么就优先往1那边走.优先的意思是如果此位置不为空就往下走,并加上对应贡献,否则走另一边,不加贡献.此时另一边不可能也为空,因为我们是把所有数看作长度为30的0-1串插入trie树,那么选一条路往下走一定能走到深度为30的点(也就是最底端).
Upd:Upd:Upd: 注意要提前insert一个0,否则hack数据(2 1 1),答案应该是2,而不insert 0答案是1.(被hack的幽怨)
CODE
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<typename T>inline void read(T &num) {
char ch; int flg = 1;
while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;
for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
num*=flg;
}
const int MAXN = 400005;
int n, x[MAXN], l[MAXN];
struct Trie {
int ch[MAXN<<5][2], tot;
inline void clear() { memset(ch, 0, sizeof ch); tot = 0; }
inline void insert(int x) {
int r = 0, i;
for(int bit = 1<<30; bit; r = ch[r][i], bit>>=1)
if(!ch[r][i=(x&bit)?1:0]) ch[r][i] = ++tot;
}
inline int calc(int x) {
int r = 0, i, res = 0;
for(int bit = 1<<30; bit; bit>>=1)
if(ch[r][i=(x&bit)?0:1]) res += bit, r = ch[r][i];
else r = ch[r][i^1];
return res;
}
}T;
int main () {
read(n);
int sum = 0, ans = 0, R = 0;
T.insert(0);
for(int i = 1; i <= n; ++i) {
read(x[i]), sum ^= x[i];
l[i] = max(l[i-1], T.calc(sum));
T.insert(sum);
}
sum = 0; T.clear(); T.insert(0);
for(int i = n; i >= 1; --i) {
sum ^= x[i];
R = max(R, T.calc(sum));
T.insert(sum);
ans = max(ans, R + l[i]); //注意这里是i不是i-1,因为L位置与R位置异或起来表示的是[L+1,R]的异或和
//也就是说此处的R其实算的是[i+1,n]的区间异或和最大值
}
printf("%d\n", ans);
}