[十二省联考 2019] 异或粽子

题意

每个非空连续区间产生一个区间异或值，从所有不同区间中选择 k 个，使异或值之和最大。

思路

这道题是 P4735 最大异或和的完美进阶。P4735 是求单个最大值，本题是求前 $k$ 大的总和。

1. 离散数学转化：消除区间与无序性

构造前缀异或和数组 $S$ ：

S[i] = a[1] \oplus a[2] \oplus \dots \oplus a[i]

边界为 $S[0] = 0$ 。任意一个粽子的美味度可以表示为：

a[l] \oplus a[l+1] \dots \oplus a[r] = S[r] \oplus S[l-1]

其中 $0 \le l-1 < r \le n$ 。

题目要求选出 $k$ 个互不相同的区间 $[l, r]$ ，使得这 $k$ 个异或值之和最大。这等价于在所有的无序对 $(i, j)$ 中选出异或值最大的 $k$ 对。

这里有一个非常实用的算法竞赛转化技巧：无序转有序。因为 $S[i] \oplus S[j] = S[j] \oplus S[i]$ ，求 $k$ 个最大的无序对，完全等价于在所有的有序对 $(i, j)$ （ $i \neq j$ ）中，求出 $2k$ 个最大的值，把它们的和加起来最后除以 2 即可。这样，我们将下标域扩展到了 $i \in [0, n]$ 且 $j \in [0, n]$ ，彻底去掉了 $i < j$ 的限制。

2. 宏观调度：大根堆多路归并——从局部第 rank 大到全局前 k 大

现在已经能在 Trie 上查到"右端点 $i$ 的第 $rank$ 大异或值"了，但怎么把每个右端点的局部最优汇总成全局前 $k$ 大？这里用到的核心算法叫多路归并（Multi-way Merge）。

我们可以把每个右端点 $i$ 想象成一口不断出水的"井"。因为 01-Trie 可以按 $rank$ 从小到大查询，所以每口井里打出来的水，体积一定是严格递减的（第 1 大 $\ge$ 第 2 大 $\ge$ 第 3 大…）。现在有 $n$ 口井，我们要从所有井里，挑出总体积最大的 $k$ 桶水。

为了高效完成这个任务，我们需要引入一个大根堆（Priority Queue）来进行宏观调度。堆里的每一个元素需要记录三个信息：(val, i, rank)，分别代表异或值、所属的右端点、当前是该端点的第几大。

具体调度流程如下：

全面撒网（初始化堆）：对于所有的右端点 $i \in [1, n]$ ，去对应的历史版本 root[i-1] 中查出它能产生的绝对最大值（即 $rank = 1$ ）。将这 $n$ 个初始状态 (val, i, 1) 全部压入大根堆。此时堆顶一定是全局真正的第 1 大值。
贪心收割（提取最大值）：弹出堆顶元素，假设它是 (val, i, rank)。将这个 val 累加到目标总和 total_ans 中。
顺藤摸瓜（懒加载补充）：必须确保当前右端点还有剩余候选组合。既然右端点 $i$ 的第 $rank$ 大组合已经被拿走，就需要让这口"井"补充下一个水位的水。如果 $rank < i$ （因为右端点 $i$ 最多只能和它前面的 $i$ 个前缀组合），就去 Trie 中查询右端点 $i$ 的第 $rank + 1$ 大的值，得到新的 next_val，将新状态 (next_val, i, rank + 1) 压回大根堆。
循环往复：重复执行步骤 2 和步骤 3，严格执行 $k$ 次。当循环结束时，total_ans 就是全局前 $k$ 大元素的和。

这种设计的精妙之处在于按需索取。在 $n=5 \times 10^5$ 的数据规模下，如果把每个端点的所有组合全查出来，内存和时间都会爆炸。而在大根堆的调度下，只有当某个端点的第 $rank$ 大值被确认为"全局前 $k$ 强"并被收割后，才会去查它的第 $rank+1$ 大值。总共只执行了 $n$ 次初始查询和 $k$ 次后续查询，完全避免了无意义的计算。

3. 微观机制：Trie 树上的第 rank 大查询

上一题 P4735 中我们用 Trie 求了最大值，顺着相反的位走就行。本题要求第 $rank$ 大，需要对普通的 01-Trie 做一点升级：在每个节点维护一个 size（或 cnt）属性。

size 表示：当前节点的子树中，一共包含了多少个数字。

当我们在 Trie 树上查询与常数 $Val$ 异或第 $rank$ 大的值时，依然从最高位往下走。假设当前 $Val$ 的这一位是 $bit$ ，为了让异或值最大，我们期望走向 expected = bit ^ 1 的分支。

此时需要做一次关键的判断：

如果 size[expected] >= rank：说明期望的分支里的数字足够多，第 $rank$ 大的数字一定就藏在这个分支里。直接走向 expected 分支，rank 不变。
如果 size[expected] < rank：说明理想的分支里数字不够。第 $rank$ 大的数字被迫落在另一个较差的分支 bit 中。走向 bit 分支，同时更新目标：去新分支里找第 rank - size[expected] 大的数字。

4. 两种解法：全局 Trie 与可持久化 Trie

本题有两种主流满分解法：

全局 01-Trie 派：把所有 $S[0..n]$ 插入一棵全局 Trie，利用"无序转有序"trick，求前 $2k$ 大有序对再除以 2。每个下标最多查询 $n$ 个其他值（排除自身 $S[i]^S[i]=0$ ），堆操作 $2k$ 次。

可持久化 01-Trie 派：像 P4735 一样，root[r] 恰好包含 $S[0..r-1]$ ，天然隔离未来数据。对于右端点 $r$ ，拿着 $S[r]$ 去 root[r] 查询第 $rank$ 大即可，严格遵守 $l \le r$ 。堆操作只需 $k$ 次，不需要翻倍除以 2。

维度	全局 01-Trie	可持久化 01-Trie
逻辑转化	转化为无序对，求前 $2k$ 大再除以 2	严格保持有序，仅在历史版本中求前 $k$ 大
空间开销	较小。只需一棵树，空间约 $N \times 32$	较大。每次插入建新链，空间约 $(N+1) \times 33$
堆操作次数	$2k$ 次	$k$ 次
思维复杂度	需要想到"无序对翻倍"的 trick	非常直观，完美继承 P4735 的区间查询思维

数据范围警报： $a_i \le 4{,}294{,}967{,}295 = 2^{32}-1$ ，达到 32 位无符号整数极限。Trie 深度必须是 32 层（第 31 到 0 位）。前 $2k$ 个最大值的总和会非常大，答案必须使用 long long。

Python 知识

heapq 是小根堆，存负值即可模拟最大堆。
堆元素 (-value, end, rank) 同时记录来源列与下一排名。
三个 array("i") 保存左右儿子和节点计数，避免上千万节点对象。
array("I") 保存 32 位无符号前缀异或。

代码

全局 01-Trie 实现（无序转有序，2k 次堆操作，最后除以 2）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-04 21:58
 * update_at: 2026-08-04 21:58
 */
// main.cpp：全局 01-Trie 解法，struct Node + get_node 风格
// 核心转化：无序对翻倍 → 在全局 Trie 上求前 2k 大有序对，最后除以 2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_OP = 500005;
// 值 ≤ 2^32-1，需要 32 位二进制（第 0..31 位）
const int MAX_DEP = 31;
const int MAX_NODES = MAX_OP * (MAX_DEP + 2);

int n;
ll k;
ll S[MAX_OP]; // 前缀异或和 S[0..n]

// 全局 01-Trie 节点
// size: 经过该节点的元素个数（以该节点路径为前缀的数字数量）
//       即子树中的元素个数，叶子节点的 size 是该具体值的出现次数
//       第 rank 大查询用 size 判断期望分支里有多少个数字
struct Node {
    int ch[2];
    int size;
};

int tot;
Node node[MAX_NODES];

auto get_node = [](){ return ++tot; };
auto bit_n = [](ll x, int i) { return (x >> i) & 1; };

// val: 插入的值
void insert(ll val) {
    int cur = 1; // 根节点（节点 1）
    node[cur].size++; // 根节点也被这个值经过，计数 +1

    for(int i = MAX_DEP; i >= 0; --i) {
        int bit = bit_n(val, i);

        // 全局 Trie：不存在的分支才新建节点
        if(node[cur].ch[bit] == 0) {
            node[cur].ch[bit] = get_node();
        }

        cur = node[cur].ch[bit];
        node[cur].size++; // 沿途每个经过的节点计数 +1
    }
}

// 在全局 Trie 中查询 val 的第 rank 大异或值
ll query(int cur, ll val, int rank) {
    ll ans = 0;
    for(int i = MAX_DEP; i >= 0; i--) {
        int bit = bit_n(val, i);
        int expected = bit ^ 1;

        int next_node = node[cur].ch[expected];
        int expected_size = node[next_node].size;

        // 期望走的分支，里面包含的数字个数是否足够支撑第 rank 大
        if(expected_size >= rank) {
            ans |= (1LL << i);
            cur = next_node;
        } else {
            // 不够用，被迫走同位分支，同时从 rank 中扣除跳过的大值个数
            rank -= expected_size;
            cur = node[cur].ch[bit];
        }
    }
    return ans;
}

// 大根堆中的元素状态
struct Element {
    ll val;   // 异或值
    int i;    // 下标
    int rank; // 当前是下标 i 的第几大组合

    bool operator<(const Element& other) const {
        return val < other.val; // 大根堆，按 val 降序
    }
};

void init(){
    std::cin >> n >> k;
    S[0] = 0;

    for(int i = 1; i <= n; ++i) {
        ll a;
        std::cin >> a;
        S[i] = S[i-1] ^ a;
    }

    // 建立全局 Trie，插入所有 S[0..n]
    get_node(); // 创建根节点（节点 1）
    for(int i = 0; i <= n; ++i) {
        insert(S[i]);
    }
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0);

    init();

    // 无序转有序：求前 2k 大有序对，最后除以 2
    // 将每个下标的第 1 大异或值放入大根堆
    priority_queue<Element> pq;
    for(int i = 0; i <= n; ++i) {
        ll max_val = query(1, S[i], 1);
        pq.push({max_val, i, 1});
    }

    ll total_ans = 0;
    ll remaining = 2LL * k;

    // 贪心提取前 2k 大
    while(remaining > 0 && !pq.empty()) {
        Element top = pq.top();
        pq.pop();

        total_ans += top.val;
        remaining--;

        // 每个下标最多与其他 n 个值配对（排除自身 S[i]^S[i]=0）
        if(top.rank < n) {
            ll next_val = query(1, S[top.i], top.rank + 1);
            pq.push({next_val, top.i, top.rank + 1});
        }
    }

    std::cout << total_ans / 2 << "\n";

    return 0;
}

可持久化 01-Trie 实现（严格有序，k 次堆操作，struct Node + size 风格）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-04 21:58
 * update_at: 2026-08-04 21:58
 */
// P5283 [十二省联考 2019] 异或粽子
// 基于可持久化 01-Trie + 大根堆多路归并
// struct Node 用 size 取代 time_id，直接维护子树元素个数
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_OP = 500005;
// 值 ≤ 2^32-1，需要 32 位二进制（第 0..31 位）
const int MAX_DEP = 31;
// 每次插入新建 MAX_DEP+2 个节点（1 个根 + MAX_DEP+1 个路径节点）
const int MAX_NODES = MAX_OP * (MAX_DEP + 2);

int n, k;
ll a[MAX_OP];
ll s[MAX_OP]; // 前缀异或和

struct Node {
    int ch[2];
    // size: 经过该节点的元素个数（以该节点路径为前缀的数字数量）
    //       即子树中的元素个数，叶子节点的 size 是该具体值的出现次数
    int size; // 🌟 改造点 1：取代 time_id，维护经过该节点的元素个数
};

int tot;
Node node[MAX_NODES];
int root[MAX_OP];

auto get_node = [](){ return ++tot; };
auto bit_n = [](ll x, int i) { return (x >> i) & 1; };

// val: 插入的值
// pre: 上一个版本的节点
// cur: 当前的新节点
void insert(ll val, int pre, int cur) {
    // 根节点元素个数 = 旧版本根节点个数 + 1
    node[cur].size = node[pre].size + 1;

    for(int i = MAX_DEP; i >= 0; --i) {
        int bit = bit_n(val, i);
        
        // 复制不需要改变的分支
        node[cur].ch[bit ^ 1] = node[pre].ch[bit ^ 1]; 
        // 创建新分支
        node[cur].ch[bit] = get_node();

        // 指针向下移动
        cur = node[cur].ch[bit];
        pre = node[pre].ch[bit];

        // 🌟 核心维护：沿途所有经过的新节点，size 都比旧版本多 1
        node[cur].size = node[pre].size + 1;
    }
}

// 🌟 改造点 2：在版本 cur 中，查找与 val 异或后第 rank 大的值
ll query(int cur, ll val, int rank) {
    ll ans = 0;
    for(int i = MAX_DEP; i >= 0; i--) {
        int bit = bit_n(val, i);
        int expected = bit ^ 1;

        int next_node = node[cur].ch[expected];
        int expected_size = node[next_node].size;

        // 检查期望走的分支，里面包含的数字个数是否足够支撑第 rank 大
        if(expected_size >= rank) {
            // 够用！第 rank 大的数一定在这个分支里，直接走
            ans |= (1LL << i);
            cur = next_node;
        } else {
            // 不够用！被迫去另一个较差的分支
            // 同时，排在前面的 expected_size 个较大值已经被跳过，需要从 rank 中扣除
            rank -= expected_size;
            cur = node[cur].ch[bit];
        }
    }
    return ans;
}

// 定义大根堆中的元素状态
struct Element {
    ll val;     // 异或和的值
    int r;      // 右端点下标
    int rank;   // 当前是 r 这个右端点的第几大组合
    
    bool operator<(const Element& other) const {
        return val < other.val; // 大根堆，按 val 降序
    }
};

void init(){
    std::cin >> n >> k;
    
    // 初始化 s[0] 的历史版本
    root[0] = get_node();
    insert(0, 0, root[0]);
    
    for(int i = 1; i <= n; ++i) {
        std::cin >> a[i];
        s[i] = s[i-1] ^ a[i];
        
        root[i] = get_node();
        insert(s[i], root[i-1], root[i]);
    }
}

signed main () {
    ios::sync_with_stdio(false); 
    cin.tie(0);
    
    init();

    priority_queue<Element> pq;

    // 🌟 改造点 3：多路归并初始化
    // 将每个右端点 r，去与其对应的历史版本 root[r-1] 组合
    // 找出每个右端点的最大异或值（rank = 1），放入大根堆
    for(int i = 1; i <= n; ++i) {
        ll max_val = query(root[i-1], s[i], 1);
        pq.push({max_val, i, 1});
    }

    ll total_ans = 0;

    // 贪心提取前 k 大
    while(k--) {
        Element top = pq.top();
        pq.pop();

        total_ans += top.val;

        // root[r-1] 中一共插入了 0 到 r-1 也就是 r 个前缀和
        // 如果当前右端点还有次大的组合（rank < r），就查出来塞回堆里
        if(top.rank < top.r) {
            ll next_val = query(root[top.r - 1], s[top.r], top.rank + 1);
            pq.push({next_val, top.r, top.rank + 1});
        }
    }

    std::cout << total_ans << "\n";
    
    return 0;
}

Python 实现（可持久化 01-Trie，array 紧凑数组版）：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74import heapq
import sys
from array import array


MAX_BIT = 31
input = sys.stdin.buffer.readline
n, required = map(int, input().split())
values = map(int, input().split())
left = array("i", [0])
right = array("i", [0])
count = array("i", [0])


def clone(node):
    left.append(left[node])
    right.append(right[node])
    count.append(count[node])
    return len(count) - 1


def insert(previous_root, value):
    root = clone(previous_root)
    count[root] += 1
    previous, current = previous_root, root
    for bit in range(MAX_BIT, -1, -1):
        if value >> bit & 1:
            child = clone(right[previous])
            right[current] = child
            previous = right[previous]
        else:
            child = clone(left[previous])
            left[current] = child
            previous = left[previous]
        current = child
        count[current] += 1
    return root


def kth_xor(root, value, rank):
    answer = 0
    for bit in range(MAX_BIT, -1, -1):
        wanted = left[root] if value >> bit & 1 else right[root]
        wanted_count = count[wanted]
        if rank <= wanted_count:
            answer |= 1 << bit
            root = wanted
        else:
            rank -= wanted_count
            root = right[root] if value >> bit & 1 else left[root]
    return answer


prefix_xor = array("I", [0])
for value in values:
    prefix_xor.append(prefix_xor[-1] ^ value)

roots = array("i", [0, insert(0, 0)])
for value in prefix_xor[1:]:
    roots.append(insert(roots[-1], value))

heap = [(-kth_xor(roots[end], prefix_xor[end], 1), end, 1)
        for end in range(1, n + 1)]
heapq.heapify(heap)
answer = 0

for _ in range(required):
    negative, end, rank = heapq.heappop(heap)
    answer -= negative
    if rank < end:
        rank += 1
        heapq.heappush(heap, (-kth_xor(roots[end], prefix_xor[end], rank), end, rank))

print(answer)

复杂度

Trie 建立 $O(32n)$ ，每次第 rank 大查询 $O(32)$ ，堆操作 $O(\log n)$ ；总时间 $O(32(n+k)+(n+k)\log n)$ ，空间 $O(32n+n)$ 。

总结

"每个右端点一列有序候选 + 堆归并"把无法枚举的 $O(n^2)$ 个区间压缩为只访问前 $k$ 个需要的值。全局 Trie 用"无序对翻倍"省空间，可持久化 Trie 用历史版本直接隔离未来数据，两者在第 $rank$ 大查询上共享同一个 size 判断逻辑。

测试点	$n$	$k$
$1$ , $2$ , $3$ , $4$ , $5$ , $6$ , $7$ , $8$	$\leqslant 10^3$	$\leqslant 10^3$
$9$ , $10$ , $11$ , $12$	$\leqslant 5 \times 10^5$	$\leqslant 10^3$
$13$ , $14$ , $15$ , $16$	$\leqslant 10^3$	$\leqslant 2 \times 10^5$
$17$ , $18$ , $19$ , $20$	$\leqslant 5 \times 10^5$	$\leqslant 2 \times 10^5$