# [题解] CODECHEF September Challenge 2015 REBXOR

## 题目描述

$$(A[l_1] \oplus A[l_1 + 1] \oplus \cdots A[r_1]) + (A[l_2] \oplus A[l_2+1] \oplus \cdots A[r_2])$$

## 样例输入1

5
1 2 3 4 5


## 样例输出1

6


## 解题思路

$$f[i] = max(f[l-1], sum[i], sum[i] \oplus sum[j])$$

$$g[i] = max(g[l+1], sum[i], sum[i] \oplus sum[j])$$

## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define Insert insert
#define Query query
#define Max max

using namespace std;
const int MAXN = 400000 + 10;
const int SIZ = 12400000 + 10;

int x = 0;
char ch = getchar();

while(ch < '0' || ch > '9')
ch = getchar();

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return x;
}

int tree[SIZ][2], cnt;
int data[MAXN], f[MAXN], g[MAXN];
int n, sum;

inline void insert(int num){
int root = 0;

for(register int i=0; i<32; i++){
int x = (num >> (32 - i - 1)) & 1;

if(!tree[root][x]){
tree[root][x] = ++cnt;
}

root = tree[root][x];
}
}

inline int query(int num){
int root = 0;
int k = 0;

for(register int i=0; i<32; i++){
int x = (num >> (32 - i - 1)) & 1;

if(tree[root][!x]){
k |= (!x) << (32 - i - 1);
root = tree[root][!x];
}else{
k |= x << (32 - i - 1);
root = tree[root][x];
}
}

return k;
}

int main(){

for(register int i=1; i<=n; i++){
}

f[1] = sum = data[1];
insert(sum);

for(register int i=2; i<=n; i++){
sum = sum^data[i];
f[i] = max(f[i-1], max(sum, sum^query(sum)));
insert(sum);
}

memset(tree, 0, sizeof(tree));
cnt = 0;
sum = 0;

g[n] = sum = data[n];
insert(sum);

for(register int i=n-1; i>=1; i--){
sum = sum^data[i];
g[i] = max(g[i+1], max(sum, sum^query(sum)));
insert(sum);
}

int ans = 0;

for(register int i=1; i<n; i++){
ans = max(ans, f[i] + g[i+1]);
}

printf("%d", ans);

return 0;
}