题目理解

我们有 $n$ 种馅料排成一排，第 $i$ 种的属性值为 $a_i$。
一个粽子可以由区间 $[l, r]$ 的馅料混合而成，美味度是这些 $a_l, a_{l+1}, \dots, a_r$ 的异或和。

我们要选 $k$ 个不同的区间，使得它们的异或和的总和最大。

---

1. 问题转化

设 $S_i$ 为前缀异或和：

$$S_i = a_1 \oplus a_2 \oplus \dots \oplus a_i$$

规定 $S_0 = 0$。

那么区间 $[l, r]$ 的异或和可以表示为：

$$X_{[l, r]} = S_r \oplus S_{l-1}$$

因此，问题变成：
在所有满足 $0 \le i < j \le n$ 的 $(i, j)$ 对中，选出 $k$ 对，使得它们的 $S_j \oplus S_i$ 的和最大。

注意这里 $i$ 对应 $l-1$，$j$ 对应 $r$，所以 $i < j$ 是必须的，且 $i$ 从 $0$ 到 $n-1$，$j$ 从 $1$ 到 $n$。

---

2. 最大化和问题

我们要求 $k$ 个不同的 $(i, j)$ 对的异或值的和的最大值。

这是一个经典问题：从 $N = n+1$ 个数 $S_0, S_1, \dots, S_n$ 中选出 $k$ 对不同的 $(p, q)$（$p < q$），使它们的异或值之和最大。

---

3. 思路分析

如果 $k$ 很小，我们可以用堆（类似”第 k 大异或对“的方法）来解。

方法：

1. 把所有的 $S_0, S_1, \dots, S_n$ 建成一棵 01-Trie。
2. 对于每个 $S_i$，我们可以在 Trie 上找到与 $S_i$ 异或值最大的 $S_j$（$j \ne i$）。
3. 用一个最大堆维护可能的候选对 $(value, i, idx)$，其中 $value$ 是 $S_i$ 与 Trie 中某个值的异或值，$idx$ 表示这是对于 $S_i$ 的第几大异或值（从大到小排序）。
4. 每次从堆顶取出最大的异或值，累加到答案，然后把这个 $S_i$ 对应的下一个小的候选异或值插入堆。

---

4. 具体步骤

4.1 Trie 结构

Trie 节点存储：

• 两个子节点指针（0 和 1）
• 经过该节点的数的数量（用于找第 $t$ 大异或值）

4.2 查询与 $x$ 异或第 $t$ 大的值

我们从高位到低位走，尽量选择与 $x$ 当前位不同的分支（为了最大化异或值），如果该分支的数量小于 $t$，则走另一分支并调整 $t$。

这里我们实际上需要的是：对于给定的 $i$，找到与 $S_i$ 异或第 $t$ 大的值（$t=1$ 是最大，$t=2$ 是次大，等等），并且保证 $j \ne i$ 且 $j$ 在 Trie 中。

---

5. 算法流程

1. 构建前缀异或数组 $S[0 \dots n]$。
2. 将 $S[0 \dots n]$ 全部插入 Trie。
3. 对每个 $i$，计算与 $S_i$ 异或最大的值及其对应的 $j$（要保证 $i \ne j$，但这里 Trie 中有重复值时需要特殊处理，不过题目 $a_i$ 不同并不能保证 $S_i$ 不同，所以可能有重复 $S$ 值，但 $(i,j)$ 不同就算不同区间，所以允许 $S$ 重复）。
4. 初始化最大堆，堆中元素为 $(xor\_value, i, rank)$，其中 $rank=1$ 表示当前取的是第 1 大的异或值。
5. 重复 $k$ 次：
   • 弹出堆顶 $(val, i, rk)$，累加 $val$ 到答案。
   • 对于这个 $i$，找它第 $rk+1$ 大的异或值，如果存在，则 $(new\_val, i, rk+1)$ 入堆。

---

6. 时间复杂度

• 建 Trie：$O(n \log M)$，$M$ 是值域，最大 $2^{32}$。
• 每次查询第 $t$ 大异或值：$O(\log M)$。
• 堆操作：$O(k \log n)$。

总复杂度 $O((n + k) \log M)$，可以接受。

---

7. 例子验证

样例：

n=3, k=2
a = [1, 2, 3]

前缀异或：

$$S_0 = 0,\ S_1 = 1,\ S_2 = 3,\ S_3 = 0$$

数：$0, 1, 3, 0$。

所有 $(i,j)$ 对的异或值（$i<j$）：

• (0,1): 1
• (0,2): 3
• (0,3): 0
• (1,2): 2
• (1,3): 1
• (2,3): 3

最大的两个是 $3$ 和 $3$，和为 $6$，符合样例。

---

8. 公式总结

设：

• 前缀异或 $S_i = \bigoplus_{t=1}^i a_t$，$S_0=0$
• 区间 $[l, r]$ 异或值 $V_{l,r} = S_r \oplus S_{l-1}$
• 我们要选 $k$ 个不同的 $(l, r)$ 使得 $\sum V_{l,r}$ 最大

等价于：

$$\max_{\substack{P \subset \{(i,j) \mid 0 \le i < j \le n\} \\ |P| = k}} \sum_{(i,j) \in P} (S_j \oplus S_i) $$

---

9. 实现细节（伪代码）

1. S[0] = 0
2. for i = 1 to n: S[i] = S[i-1] xor a[i]
3. Build Trie with all S[0..n]
4. max_heap = []
5. for i = 0 to n:
      value, idx = query_max_xor(S[i])  # 保证 idx != i 如果需要，可以查两次
      push (value, i, 1) to max_heap
6. ans = 0
7. for _ in range(k):
      pop (v, i, rk) from heap
      ans += v
      next_val = query_kth_xor(S[i], rk+1)  # 第 rk+1 大的异或值
      if next_val exists:
          push (next_val, i, rk+1) to heap
8. output ans

---

这样我们就得到了一个高效的 $O((n+k)\log M)$ 解法，可以处理 $n=5\times 10^5, k=2\times 10^5$ 的大数据。