Nikitosh 和异或

题面

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;

int bit[32];
int n, a[5211314], sum[5211314];
int l[5211314], r[5211314];

struct Trie {
	int trie[5211314 << 1][2], tot = 1;
	inline void Clear() {
		memset(trie, 0, sizeof(trie));
		return;
	}
	inline void Insert(int a) {
		int p = 1;
		for (int i = 31; i >= 0; -- i) {
			bool flag = (bit[i] & a);
			if (trie[p][flag] == 0) {
				trie[p][flag] = ++ tot;
			}
			p = trie[p][flag];
		}
	}
	inline int Query(int x) {
		int p = 1, ans = 0;
		for (int i = 31; i >= 0; -- i) {
			bool flag = !(bit[i] & x);
			if (trie[p][flag] != 0) {
				p = trie[p][flag];
				ans += flag;
			}
			else {
				flag = !flag;
				p = trie[p][flag];
				ans += flag;
			}
			if (i != 0) ans <<= 1;
		}
		return (x ^ ans);
	}
}tree;

int main() {
	bit[0] = 1;
	for (int i = 1; i <= 31; ++ i) {
		bit[i] = bit[i - 1] << 1;
	}
	cin >> n;
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i];
	}
	tree.Insert(0);
	//要Insert（0）,因为题里的l可以等于r
	for (int i = 1; i <= n; ++ i) {
		sum[i] = (sum[i - 1] ^ a[i]);
		tree.Insert(sum[i]);
		l[i] = max(l[i - 1], tree.Query(sum[i]));
		//查询到i的前缀最长异或和
	}
	tree.Clear();
	//记得清空
	memset(sum, 0, sizeof(sum));
	tree.Insert(0);
	for (int i = n; i >= 1; -- i) {
		sum[i] = (sum[i + 1] ^ a[i]);
		tree.Insert(sum[i]);
		r[i] = max(r[i + 1], tree.Query(sum[i]));
		//查询到i的后缀最长异或和
	}
	int ans = 0;
	for (int i = 1; i <= n - 1; ++ i) {
		ans = max(ans, l[i] + r[i + 1]);
		//注意范围
	}
	printf("%d\n", ans);
	return 0;
}