У вас есть массив целых неотрицательных чисел $$$a_1, a_2, \ldots, a_n$$$.
Значение подотрезка длины $$$\ge 2$$$: $$$a[l, r] = [a_l, a_{l+1}, \ldots, a_r]$$$ — это минимальное значение $$$a_i \oplus a_j$$$ такое, что $$$l \le i < j \le r$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.
Вам нужно найти $$$k$$$-е наименьшее значение среди всех подотрезков длины $$$\ge 2$$$.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$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$$$.
Для каждого набора входных данных в отдельной строке выведите $$$k$$$-ю порядковую статистику среди значений всех подотрезков длины хотя бы $$$2$$$.
45 21 2 3 4 52 14 34 61 2 4 85 91 2 3 4 5
1 7 12 3
В первом наборе входных данных мы имеем такие подотрезки и наименьшие значения побитового исключающего ИЛИ пары элементов:
$$$[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$$$.
Название |
---|