CF1983F.array-value

你有一个非负整数数组 $a_1, a_2, \ldots, a_n$。

一个长度 $\ge 2$ 的子数组 $a[l, r] = [a_l, a_{l+1}, \ldots, a_r]$ 的值定义为 $\min(a_i \oplus a_j)$，其中 $l \le i < j \le r$，$\oplus$ 表示异或运算。

你需要找出所有长度不少于 $2$ 的子数组的值中第 $k$ 小的那个。

输入的第一行为测试用例数 $t$（$1 \le t \le 2 \cdot 10^4$）。

每个测试用例的第一行为两个整数 $n$ 和 $k$（$2 \le n \le 10^5$，$1 \le k \le \frac{n\cdot(n-1)}{2}$）。

每个测试用例的第二行为 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$）——即数组本身。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出所有长度不少于 $2$ 的子数组的值中第 $k$ 小的那个。

在第一个测试用例中，各子数组的最小异或对为：

$[1,2]: 3$

$[2,3]: 1$

$[3,4]: 7$

$[4,5]: 1$

$[1,2,3]: 1$

$[2,3,4]: 1$

$[3,4,5]: 1$

$[1,2,3,4]: 1$

$[2,3,4,5]: 1$

$[1,2,3,4,5]: 1$

排序后为：$1, 1, 1, 1, 1, 1, 1, 1, 3, 7$。因此，第二小的元素为 $1$。

由 ChatGPT 4.1 翻译