$\oplus$ 表示异或。

简化题意

有一个长度为 $n$ 的序列 $a$，现在要选出 $k$ 个互不相同的区间 $[l, r] \ (1 \le l \le r \le n)$，使得每一个区间的异或和最大（一个区间 $[l, r]$ 的异或和是 $a_l \oplus a_{l + 1} \oplus \cdots \oplus a_r$）。

转化问题

首先设 $s_0 = 0, s_i$ 为 $a_1 \oplus a_2 \oplus \cdots \oplus a_i$，因为 $x \oplus x = 0$，所以：

$s_r \oplus s_{l - 1}$

$= a_1 \oplus a_2 \oplus \cdots \oplus a_r \oplus a_1 \oplus a_2 \oplus \cdots \oplus a_{l - 1}$

此时 $a_1 \sim a_{l - 1}$ 都被抵消了，只剩下 $a_l \sim a_r$，于是一个区间 $[l, r]$ 的异或和就等于 $s_{l - 1} \oplus s_r$。于是一个区间的异或和就变成了 $s_a \oplus s_b \ (0 \le a < b \le n)$。

这种转化是一种常见的套路，请各位务必掌握。

然后，要选出 $k$ 个互不相同的区间并让他们的异或和最大，显然选出的区间是异或和前 $k$ 大的几个区间。

但是要求选出的 $s_a \oplus s_b$ 需要满足 $a < b$，怎么办？

由于 $a \oplus b = b \oplus a$，所以 $s_a \oplus s_b$ 与 $s_b \oplus s_a$ 相同，我们使 $k \to 2k$，输出答案时除以二即可。

转化结果

有一个长度为 $n + 1$ 的序列 $s$，现在要选出 $2k$ 个互不相同的数对 $(a, b)$，使得每一个数对 $(a, b)$ 的权值 $s_a \oplus s_b$ 之和最大。