meepo's Blog

Description

Input

Output

Sample Input

Sample Output

HINT

Source

    Orz 豆豆神犇。。。全机房第一个做这道题的。。然后教会了全机房——>

                             http://qiancl.is-programmer.com/

    作者道题之前需要先知道一个规律。。。xor的逆运算也是xor。。所以我们可以通过前缀得出任意一段的xor值。。。对于求一个位置pos为结尾的xor值最大的一段，可以在它前面的前缀xor中从二进制高位向低位找是否可以使这个位置为1。。。然后后缀也做一遍。。。最后就可以O(n)扫一遍得出答案了

    至于维护之前的xor值我们可以用一个字母树维护。。每次在树上找出xor最大。。记录后把当前这个店的前缀xor插入树中

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 4e5;
int a[N],b[N],c[N],L[N],R[N],f[40],ans,n,next[15100000][2],len,cnt,Max;
int read(){
	int x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
void Work(int x){
	memset(f,0,sizeof(f));len = 0;
	while (x){f[++len] = x&1;x>>=1;}
}
int Query(){
	int res = 0,now = 0;
	for (int i=32;i;i--){
		if (next[now][f[i]==0]) {res+=(1<<(i-1));now = next[now][f[i]==0];}
		else now = next[now][f[i]];
	}
	return res;
}
void Insert(){
	int now = 0;
	for (int i=32;i;i--){
		if (!next[now][f[i]]){++cnt;next[now][f[i]] = cnt;now = cnt;}
		else now = next[now][f[i]];
	}
}
int main(){
	n = read();
	for (int i=1;i<=n;i++) a[i] = read();
	for (int i=1;i<=n;i++) b[i] = a[i]^b[i-1];
	for (int i=n;i;i--) c[i] = a[i]^c[i+1];
	Work(0);Insert();
	for (int i=1;i<=n;i++){
		Work(b[i]);
		L[i] = max(b[i],Query());
		Insert();
	}
	memset(next,0,sizeof(next));cnt = 0;
	Work(0);Insert();
	for (int i=n;i;i--){
		Work(c[i]);
		R[i] = max(c[i],Query());
		Insert();
	}
	for (int i=1;i<=n;i++){
		Max = max(Max,L[i]);
		ans = max(Max+R[i],ans);
	}
	printf("%d",ans);
}