题目大意

给定一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$（$n\ge 2$）。
对于任意长度至少为 $2$ 的子数组 $a[l,r]$，定义其“值”为子数组中所有不同位置元素异或的最小值，即

现在要找出所有这样的子数组（共 $\frac{n(n-1)}{2}$ 个）的值，将它们从小到大排序后，求第 $k$ 小的值。

解题思路

1. 问题转化

直接枚举所有子数组并计算最小值是不可行的，因为 $O(n^2)$ 太大。
常见技巧是二分答案：设答案为 $V$，则我们需要判断有多少个子数组的“值” $\le V$。记这个数量为 $\mathrm{cnt}(V)$。
若 $\mathrm{cnt}(V) \ge k$，则答案 $\le V$，否则答案 $>V$。
通过二分 $V$ 可以将原问题转化为判定问题。

二分上界：因为 $a_i\le 10^9<2^{30}$，所以任何两个数的异或最大不超过 $2^{30}-1$，可以取上界为 $2^{30}$。

2. 判定问题：统计“值 $\le X$”的子数组个数

对于固定的 $X$，我们想要数出有多少个子数组满足其内部的最小异或值不超过 $X$。

关键观察

对于一个子数组，若我们不断增加它的左端点（即删除左边元素），子数组的长度变小，最小异或值只会增大或不变（因为删除了某些数对，可能消除了较小的异或值）。
因此，对于固定的右端点 $r$，子数组 $[l,r]$ 的最小异或值关于 $l$ 是单调不减的。
这允许我们使用双指针（滑动窗口）：

• 维护一个窗口 $[L, r]$，并实时维护该窗口内所有元素两两异或的最小值。
• 当我们向右移动 $r$ 时，将 $a_r$ 加入窗口，窗口的最小异或值可能会变小。
• 接着，只要窗口的最小异或值 $\le X$，我们就将左端点 $L$ 向右移动（删除 $a_L$），直到窗口的最小异或值 $> X$。
• 此时，对于当前右端点 $r$，所有以 $r$ 为右端点且左端点小于 $L$ 的子数组 $[l,r]$（$1\le l<L$）都必然满足其最小异或值 $\le X$。
  理由：$[l,r]$ 包含了 $[L,r]$ 中的元素，还多了左边的元素，所以它的最小异或值不会大于 $[L,r]$ 的最小异或值，而 $[L,r]$ 已经大于 $X$，因此更长的区间可能包含更小的异或值，我们需要的是 $\le X$ 的区间。实际上，当窗口 $[L,r]$ 的最小异或值 $>X$ 时，更长的区间（$l<L$）因为包含更多元素，可能产生更小的异或，所以可能 $\le X$。因此所有 $l<L$ 都满足条件，数量恰好为 $L-1$。

对每个 $r$ 累加 $(L-1)$，即得到 $\mathrm{cnt}(X)$。

3. 动态维护窗口的最小异或值

我们需要一个数据结构，支持：

• 插入一个数
• 删除一个数
• 查询当前集合中任意两个数异或的最小值

一个重要结论：对于一个有序的整数集合，最小异或值一定出现在相邻元素之间。
证明：设 $x<y<z$，则 $x\oplus z \ge \min(x\oplus y,\ y\oplus z)$。因此只需维护排序后相邻两个数的异或值，取最小值即可。

具体实现：

• 用一个 multiset（或平衡树）维护当前窗口中的所有数（按值排序）。
• 同时维护另一个 multiset 存放相邻数的异或值。
• 插入 $x$：找到它的前驱和后继，更新相邻异或值。
• 删除 $x$：同样更新相邻异或值。
• 查询最小值：取第二个 multiset 的最小值（若元素个数 $<2$ 则返回无穷大）。

每次操作 $O(\log n)$，窗口滑动总复杂度 $O(n\log n)$。

4. 算法流程

1. 读入 $n,k$ 和数组 $a$（下标从 $1$ 开始）。
2. 二分答案 $V$，范围 $[0, 2^{30}-1]$：
   • 计算 $\mathrm{cnt}(V)$。
   • 若 $\mathrm{cnt}(V)\ge k$，则 $ans\leftarrow V$，且 $high\leftarrow V$；
   • 否则 $low\leftarrow V+1$。
3. 输出最终 $ans$。

时间复杂度：二分 $O(\log MAX)=30$ 次，每次判定 $O(n\log n)$，总 $O(30n\log n)$，可承受 $n\le 10^5$。

注意事项

• $k$ 可能达到 $\frac{n(n-1)}{2}\approx 5\times10^9$，需要使用 long long 类型。
• 数据范围保证所有测试用例的 $n$ 之和 $\le 10^5$，因此总体复杂度 $\sum 30n\log n$ 可接受。
• 滑动窗口中的左指针 $L$ 初始为 $1$，且 $L\le r$，当 $L=r$ 时窗口只有一个元素，此时不存在异或对，最小值设为无穷大。
• 实现时，相邻异或值集合需要支持重复值（因为异或结果可能相同），使用 multiset 而不是 set。

总结

本题的核心是利用单调性将最小值问题转化为判定问题，再通过滑动窗口 + 有序集合维护相邻异或值来高效统计。
该技巧在许多求“子数组最小异或值”或“子数组最小差值”的第 $k$ 小问题中都可以使用。