Codeforces 282E. Sausage Maximization http://codeforces.com/problemset/problem/282/E 按位用trie树维护

CF282E.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int maxn = 100010;

struct TrieNode {
	int next[2];

	void init() {
		next[0] = next[1] = -1;
	}
};

struct TrieTree {

	TrieNode tree[44*maxn];
	int cnt;

	void init() {
		cnt = 1;
		for (int i = 0; i < 44*maxn; i++)
			tree[i].init();
	}

	void insert(long long val) {
		int u = 0;
		for (int i = 44; i >= 0; i--) {
			int id = ((1LL<<i)&val) != 0;
			if (tree[u].next[id] == -1)
				tree[u].next[id] = cnt++;
			u = tree[u].next[id];
		}
	}

	long long find(long long val) {
		long long res = 0;
		int u = 0;
		for (int i = 44; i >= 0; i--) {
			int id = ((1LL<<i)&val) == 0;
			if (tree[u].next[id] == -1)
				id ^= 1;
			res = res * 2LL + id;
			u = tree[u].next[id];
		}
		return res;
	}

};

TrieTree tree;

int n;
long long a[maxn];

int main() {
	long long cur = 0, sum = 0, ans = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum ^= a[i];
	}
	tree.init();
	ans = sum;
	tree.insert(0LL);
	for (int i = 0; i < n; i++) {
		cur ^= a[i]; sum ^= a[i];
		tree.insert(cur);
		long long tmp = tree.find(sum);
		ans = max(ans, tmp^sum);
	}
	cout << ans << endl;
	return 0;
}