题目大意

「十二省联考 2019」异或粽子（Luogu 5283）

给定一个长度为 $n$ 的数列 $a_1, a_2, \cdots, a_n$ ，问区间异或和前 $k$ 大的区间的异或和之和。

数据范围： $n \le 5 \times 10^5, m \le 2 \times 10^5, 0 \le a_i < 2^{32}$ 。

思路分析

我们设 $S_i$ 表示前 $i$ 个数的异或和，那么区间 $[l, r]$ 的异或和等于 $S_{l - 1} \bigoplus S_{r}$ 。由于 $x \bigoplus y = y \bigoplus x$ ，本题的答案等于取 $2k$ 个 $S_i \bigoplus S_j$ 最大的 $(i, j) (0 \le i, j \le n, i \neq j)$ 求和再除以 $2$ 。又由于 $x \bigoplus x = 0$ ，所以 $i \neq j$ 的限制也可以去掉。这样，我们使用字典树 + 堆来维护即可。时间复杂度 $O((n + m) \log n)$ 。

代码实现

1	#include <cstdio>
2	#include <cstring>
3	#include <queue>
4	using namespace std;
5	typedef long long ll;
6	typedef pair<ll, int> P;
7
8	const int maxn = 5e5, maxm = 32, maxk = maxn * maxm;
9	int n, k, tot, ch[maxk + 3][2], sz[maxk + 3], cnt[maxn + 3];
10	ll a[maxn + 3];
11	priority_queue<P> H;
12
13	void insert(ll num) {
14	int x = 1;
15	for (int i = maxm - 1; ~i; i--) {
16	int k = num >> i & 1;
17	if (!ch[x][k]) {
18	ch[x][k] = ++tot;
19	}
20	x = ch[x][k], sz[x]++;
21	}
22	}
23
24	ll query(int y, ll num) {
25	int x = 1;
26	ll ans = 0;
27	for (int i = maxm - 1; ~i; i--) {
28	int k = num >> i & 1;
29	if (y <= sz[ch[x][k ^ 1]]) {
30	ans \|= 1ll << i;
31	x = ch[x][k ^ 1];
32	} else {
33	y -= sz[ch[x][k ^ 1]];
34	x = ch[x][k];
35	}
36	}
37	return ans;
38	}
39
40	int main() {
41	scanf("%d %d", &n, &k), k *= 2;
42	for (int i = 1; i <= n; i++) {
43	scanf("%lld", &a[i]), a[i] ^= a[i - 1];
44	}
45	tot = 1;
46	for (int i = 0; i <= n; i++) {
47	insert(a[i]);
48	}
49	for (int i = 0; i <= n; i++) {
50	cnt[i] = 1;
51	H.push(P(query(1, a[i]), i));
52	}
53	ll ans = 0;
54	for (int i; k--; ) {
55	P x = H.top();
56	H.pop(), i = x.second;
57	ans += x.first, cnt[i]++;
58	if (cnt[i] <= n + 1) {
59	H.push(P(query(cnt[i], a[i]), i));
60	}
61	}
62	printf("%lld\n", ans / 2);
63	return 0;
64	}