bzoj3261: 最大异或和 （可持久化trie树）

题目链接

题解

看到异或和最大就应该想到01 trie树

我们记\(S_i\)为前i项的异或和

那么我们的目的是最大化\(S_n\)\(S_{j-1}\) \((l <= j <= r)\) （注意是\(j-1\), 所以l和r都要减1）

\(S_n\)^\(x\)已经固定， 那么我们可以把\(S_j\)放入trie树搞

那么怎么处理区间呢？

类似主席树

记录一下\([1-i]\)每个节点被多少个数经过

那么两棵trie树相减，就得到了 \([l-r]\)这段区间的信息

然后就是经典的模型了

Code

#include<bits/stdc++.h>

const int N = 600010, M = 25;

#define LL long long

#define RG register

int ch[N*30][2], sum[N*30], root[N], cnt, tot, ans;

using namespace std;

inline int gi() {

	RG int x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar();

	if (c == '-') c = getchar(), f = 1;

	while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();

	return f ? -x : x;

}

void insert(int &now, int x, int dep) {

	sum[++cnt] = sum[now]+1;

	ch[cnt][0] = ch[now][0]; ch[cnt][1] = ch[now][1];

	now = cnt;

	if (dep < 0) return ;

	insert(ch[now][(x >> dep) & 1], x, dep-1);

	return ;

}

void query(int rt1, int rt2, int x, int dep) {

	if (dep < 0) return ;

	int k = (x >> dep)&1;

	if (sum[ch[rt2][k^1]]-sum[ch[rt1][k^1]] > 0) {

		ans |= (1 << dep);

		query(ch[rt1][k^1], ch[rt2][k^1], x, dep-1);

	}

	else query(ch[rt1][k], ch[rt2][k], x, dep-1);

	return ;

}

int main() {

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	int n = gi(), m = gi();

	for (int i = 1; i <= n; i++) {

		int x = gi();

		tot ^= x; root[i] = root[i-1];

		insert(root[i], tot, M-1);

	}

	for (int i = 1; i <= m; i++) {

		char c = getchar();

		while (c != 'A' && c != 'Q') c = getchar();

		if (c == 'A') {

			int x = gi();

			tot ^= x;

			root[n+1] = root[n];

			insert(root[++n], tot, M-1);

		}

		else {

			int l = gi()-1, r = gi()-1, x = gi();

			ans = 0;

			query(root[l-1], root[r], tot^x, M-1);

			if (!l) ans = max(ans, tot^x);

			printf("%d\n", ans);

		}

	}

	return 0;

}