题目地址：P5283 [十二省联考2019]异或粽子

题意

前 $k$ 大区间异或和。

思路

一个很基础的转化是，我们可以 $O(n)$ 求出前缀异或和 $s_0, s_1, ..., s_n$ 。

那么显然 $xor_{i=l}^{r} = s_{l-1}\ xor\ s_r$ 。

题意转化为，在 $s_0, s_1, ..., s_n$ 这 $n+1$ 个数中，选出 $k$ 对 $(s_i, s_j)(i<j)$ ，使每对的异或值的和最大。

暴力分

注意到有 $60$ 分的数据满足 $n \leq 1000$ ，而上述所说的数对一共有 $O(n^2)$ 个。

那么我们可以把每一对的异或值都插入一个大根堆（优先队列）中，然后弹出 $k$ 次最大值，弹出的所有值的和就是最终答案。

#include <bits/stdc++.h>
#define ui unsigned int
#define ull unsigned long long
using namespace std;
const int N = 5e5 + 6;
int n, k;
ui a[N], s[N];
priority_queue<ui> q;
ull ans;

inline ui rd() {
	ui x = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x;
}

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) a[i] = rd(), s[i] = s[i-1] ^ a[i];
	for (int l = 1; l <= n; l++)
		for (int r = l; r <= n; r++)
			q.push(s[r] ^ s[l-1]);
	while (k--) ans += q.top(), q.pop();
	cout << ans << endl;
	return 0;
}

注意：由于这道题 $a$ 数组的数据范围为 $0 \leq ai​ \leq 4294967295$ ，所以要开unsigned int（当然long long也行）。

正解

前置芝士

可持久化Trie

洛谷似乎并没有可持久化Trie的模板2333。

首先你要知道可持久化。

其次你要会Trie，并且要会这道题所要使用的01Trie。

如果这两者都会了，那么请先去把P4735 最大异或和A掉。

A掉这道题之后，你就应该知道如何求在序列 $a$ 的一个给定区间 $[l, r]$ 中选择一个数 $i$ 使 $a_i$ 与另一个给定的值异或起来最大。

简要的思路是，建立可持久化Trie，在给定区间的Trie上贪心的优先选择与给定值当前位相反的节点（指针）。

本题思路

一开始，对于每个右端点 $r$ ，在前缀异或和序列 $s$ 的区间 $[0,r-1]$ 选择一个左端点 $l$ 使 $s_l$ 与 $s_r$ 异或起来最大，并将描述这个值的所有信息以这个值为关键字插入一个大根堆中。

描述这个值所需要的信息有：

1. 这个值的大小；
2. 这个值左端点的选择区间；
3. 这个值的左右端点。

可以用一个结构体记录，也可以用若干个pair记录，我的代码实现中是用的后者。

仍然弹出 $k$ 次堆中的最大值，那么弹出的所有值的和就是最终答案。

但是在弹出的同时也在不断的插入。

假设此时弹出来值及其描述信息为：

1. 这个值为 $x$ ；
2. 这个值左端点的选择区间为 $[L,R]$；
3. 这个值的左右端点为 $l,r$。

首先将 $x$ 加入答案。

然后将选择区间以 $l$ 为界限分成两段 $[L,l-1], [l+1,R]$ ，分别在这两个区间中选择与 $s_r$ 最大的异或值，将这个值及其描述信息插入大根堆中。

正确性

不言而喻。

本题代码实现比较复杂，细节比较多，我的代码仅供参考，建议自己清楚思路后独立AC。

#include <bits/stdc++.h>
#define ui unsigned int
#define ull unsigned long long
#define pii pair<int, int>
#define X first
#define Y second
#define mp make_pair
using namespace std;
const int N = 5e5 + 6;
int n, m, trie[N<<6][2], late[N<<6], rt[N], t;
ui a[N];
ull ans;
priority_queue<pair<ui, pair<pii, pii> > > q;

inline ui rd() {
	ui x = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9')
		x = x * 10 + (ch - '0'), ch = getchar();
	return x;
}

void ins(int i, int k, int p, int o) {
	if (k < 0) return late[o] = i, void();
	int c = (a[i] >> k) & 1;
	if (p) trie[o][c^1] = trie[p][c^1];
	trie[o][c] = ++t;
	ins(i, k - 1, trie[p][c], trie[o][c]);
	late[o] = max(late[trie[o][0]], late[trie[o][1]]);
}

int ask(ui x, int k, int o, int p) {
	if (k < 0) return late[o];
	int c = (x >> k) & 1;
	return ask(x, k - 1, trie[o][c^(late[trie[o][c^1]]>=p)], p);
}

int main() {
	cin >> n >> m;
	late[0] = -1;
	ins(0, 31, 0, rt[0] = ++t);
	for (int i = 1; i <= n; i++) {
		a[i] = rd() ^ a[i-1];
		ins(i, 31, rt[i-1], rt[i] = ++t);
		int j = ask(a[i], 31, rt[i-1], 0);
		q.push(mp(a[j] ^ a[i], mp(mp(0, i - 1), mp(j, i))));
	}
	while (m--) {
		ans += q.top().X;
		int l = q.top().Y.Y.X, i = q.top().Y.Y.Y;
		pii k = q.top().Y.X;
		q.pop();
		if (l != k.Y) {
			int j = ask(a[i], 31, rt[k.Y], l + 1);
			q.push(mp(a[j] ^ a[i], mp(mp(l + 1, k.Y), mp(j, i))));
		}
		if (l != k.X) {
			int j = ask(a[i], 31, rt[l-1], k.X);
			q.push(mp(a[j] ^ a[i], mp(mp(k.X, l - 1), mp(j, i))));
		}
	}
	cout << ans << endl;
	return 0;
}