[bzoj 4260] Codechef REBXOR

给一个长度为N的序列A, 求(A[l1] xor A[l1+1] xor ... xor A[r1]) + (A[l2] xor A[l2+1] xor ... xor A[r2])的最大值. (2≤N≤4*10^5, 0≤Ai≤10^9) 从前往后, 从后往前各建一次前缀/后缀异或和的Trie树, 贪心, 枚举l2, 加上(A[l1] xor ... xor A[r1])的前缀max和, 更新答案.

对于一些前缀, 后缀的信息, 通过控制加入顺序, 可以不用持久化而完成和持久化一样的工作.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)
#define bin(x, k) ((x)>>(k)&1)
using namespace std;
const int D = 30, MAX_N = 4e5;

struct Node {
	Node* ch[2];
} nodes[(D+1)*(MAX_N+1)], * root, * cur;

int S, a[MAX_N+1], pre[MAX_N+1];

inline Node* new_node()
{
	*cur = (Node){0, 0};
	return cur++;
}

void insert(Node* &o, int x, int k)
{
	if (!o) o = new_node();
	if (k >= 0) insert(o->ch[bin(x, k)], x, k-1);
}

int query(Node* o, int x, int k)
{
	if (k < 0) return 0;
	int b = bin(x, k)^1;
	return o->ch[b] ? 1<<k | query(o->ch[b], x, k-1) : query(o->ch[b^1], x, k-1);
}

inline void init()
{
	cur = nodes;
	S = 0;
	insert(root = 0, 0, D-1);
}

int main()
{
	int n, ans = 0;
	scanf("%d", &n);
	init();
	For (i, 1, n) {
		scanf("%d", &a[i]);
		pre[i] = max(pre[i-1], query(root, S ^= a[i], D-1));
		insert(root, S, D-1);
	}
	init();
	Down (i, n, 2) {
		ans = max(ans, pre[i-1] + query(root, S ^= a[i], D-1));
		insert(root, S, D-1);
	}
	printf("%d\n", ans);
	return 0;
}