题目大意
给定一个长度为 $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 | |
2 | |
3 | |
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 | } |