异或粽子——玄学复杂度的神奇分治法

## 异或粽子——玄学复杂度的神奇分治法 ### 引子 似乎大家的做法大多都用到 Trie？蒟蒻不熟悉 Trie，更不会可持久化 Trie，所以…… 前几天听学长说这题是毒瘤 Trie，没想到今天模拟考就用了这套题……当时看到题面的时候我的内心是崩溃的。 于是——赶紧写个暴力！ 暴力分还是挺好拿的——枚举所有连续子段，求出其异或值，把所有的连续子段的异或值排序，取前 $k$ 大相加即可。写完暴力，不甘心只拿这些分的我就开始想一个能拿更多部分分的算法。 ### 思考 看到位运算，我想到了按位处理。 考虑最高位——只有最高位为 $0$ 的数和最高位为 $1$ 的数异或起来才能最高位为 $1$。自然，最高位为 $1$ 的异或值一定比最高位为 $0$ 的异或值大。 因此，如果最高位为 $1$ 的异或值已经多于 $k$ 个，那么前 $k$ 大只能从这些较大的异或值里取；否则，所有最高位为 $1$ 的异或值都在答案范围内，并且还要取一些最高位为 $0$ 的较小异或值补足 $k$ 个。 上面就是本解法的基本思想。