# BZOJ4260 Codechef REBXOR

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

01字典树。当然会了一点简单的题，这个还是没有一点思路，之前的都是跑一个数的最大值，这里是区间。这里用到了简单的异或性质

• $$0\oplus a = a, a\oplus a = 0$$

$$pre[i]\oplus pre[j] = a[i+1]\oplus a[i+2]\oplus\dots\oplus a[j], i < j$$，后缀同理

#include<bits/stdc++.h>
using namespace std;
const int N = 400010;
const int inf = 0X3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
typedef long long ll;

int n;
int a[N];
int pre[N], suf[N];
int dp[N];
int tri[32 * N][2];
int val[32 * N];
int tot;

void init() {
memset(tri, 0, sizeof(tri));
memset(val, 0, sizeof(val));
tot = 1;
}

void Insert(int x) {
int u = 0;
for (int i = 31; i >= 0; i--) {
int bit = (x & (1 << i)) ? 1 : 0;
if (!tri[u][bit])
tri[u][bit] = tot++;
u = tri[u][bit];
}
val[u] = x;
}

int Query(int x) {
int u = 0;
for (int i = 31; i >= 0; i--) {
int bit = (x & (1 << i)) ? 1 : 0;
if (tri[u][bit ^ 1])
u = tri[u][bit ^ 1];
else
u = tri[u][bit];
}
return x ^ val[u];
}

int main() {
while(~scanf("%d", &n)) {
init();
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
pre[0] = suf[n + 1] = 0;
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] ^ a[i];
for (int i = n; i >= 1; i--) suf[i] = suf[i + 1] ^ a[i];
Insert(pre[0]);
for (int i = 1; i <= n; i++) {
dp[i] = max(dp[i - 1], Query(pre[i]));
Insert(pre[i]);
}
init();
Insert(suf[n + 1]);
int ans = -1;
for (int i = n; i >= 1; i--) {
ans = max(ans, Query(suf[i]) + dp[i - 1]);
Insert(suf[i]);
}
printf("%d\n", ans);
}
}


BZOJ4260 Codechef REBXOR

(0)
(0)