nkoj 1873 Cow XOR奶牛异或

题目大意：

给了你一个长度为 $n$ 的序列 $a$，请找出一段区间，使得这个区间的异或和最大，如果异或和相同选右端点大的，还是相同选左端点大的。

$1\le n\le 10^5,1\le a_i\le 2^{21}-1$。

做一遍前缀和，变为选择两个数使其异或和最大。

01-trie，把每个数按照二进制拆分，由于最多只会到 $2^{20}$，所以可以把 $2^{21}$ 作为trie的根节点，然后每个节点有左儿子和右儿子，分别表示 $0$ 和 $1$，最后根到叶子的路径就表示了一个数。

那么查询的时候只需要逐个比较，先考虑最高位和当前数不同的，再考虑第二高位不同的……如此下去直到叶节点，注意稍微处理异或和相同选右端点大，还相同考虑左端点大这一限制。

#include <cstdio>

inline int min(const int x, const int y) {return x < y ? x : y;}
int s[100005], ch[3000005][2], value[3000005], n, l, r, ans, ret, tot = 1;
int query(int O, int x, int _bit) {
	if (_bit == -1) return ret = value[O], 0;
	if (s[x] & (1 << _bit)) {
		if (ch[O][0]) return query(ch[O][0], x, _bit - 1) + (1 << _bit);
		else return query(ch[O][1], x, _bit - 1);
	} else {
		if (ch[O][1]) return query(ch[O][1], x, _bit - 1) + (1 << _bit);
		else return query(ch[O][0], x, _bit - 1);
	}
}
void insert(int O, int x, int _bit) {
	if (_bit == -1) {
		if (!value[O] || value[O] < x) value[O] = x;
		return;
	}
	if (s[x] & (1 << _bit)) insert(ch[O][1] ? ch[O][1] : ch[O][1] = ++ tot, x, _bit - 1);
	else insert(ch[O][0] ? ch[O][0] : ch[O][0] = ++ tot, x, _bit - 1);
}

int main() {
	scanf("%d", &n);
	insert(1, 0, 20);
	for (int i = 1; i <= n; ++ i) {
		int x, tmp;
		scanf("%d", &x);
		s[i] = s[i - 1] ^ x;
		if (ans < (tmp = query(1, i, 20))) ans = tmp, l = ret, r = i;
		insert(1, i, 20);
	}
	if (n == 1 && s[1] == 0) return puts("0 1 1"), 0;
	printf("%d %d %d\n", ans, l + 1, r);
	return 0;
}