array-value
Contest: Codeforces Round 956 (Div. 2) and ByteRace 2024
Difficulty rating: 2500
Tags: binary search, bitmasks, data structures, greedy, two pointers

You have an array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$.

The value of a sub-array of length $$$\ge 2$$$, $$$a[l, r] = [a_l, a_{l+1}, \ldots, a_r]$$$ is the minimum value of $$$a_i \oplus a_j$$$ such that $$$l \le i < j \le r$$$, where $$$\oplus$$$ is the xor (exclusive-or) operator.

You have to find the $$$k$$$-th smallest value over all sub-arrays of length $$$\ge 2$$$.

Input format:
The first line of the input contains multiple test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$).

The first line of each test case contains integer numbers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le \frac{n\cdot(n-1)}{2}$$$).

The second line of the input contains $$$n$$$ non-negative integer numbers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the array itself.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
Print the $$$k$$$-th smallest value obtained over all subarrays of length at least $$$2$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first testcase, we have subarrays with their smallest exclusive-or pair as:

$$$[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$$$

The sorted order would be: $$$1, 1, 1, 1, 1, 1, 1, 1, 3, 7$$$. Therefore, the second smallest element would be $$$1$$$.

Example input:
4
5 2
1 2 3 4 5
2 1
4 3
4 6
1 2 4 8
5 9
1 2 3 4 5

Example output:
1
7
12
3

Editorial:
We can binary search on the the value of the $$$k$$$th-smallest and maintain the number of subarrays with xor-pair less than the value. This way, we can find the $$$k$$$th-smallest value easily.
In order to maintain the number of subarrays, we can use our popular xor data structure called trie.
For a given binary searched value, we will traverse from left to right, putting in the values of the array in our trie with their highest corresponding indices.
For a fixed index $$$i$$$, we would like to find the highest index $$$j<i$$$ such that the subarray from $$$[j,i]$$$ contains xor-pair less than the fixed upper bound. Then all subarrays with their left end between $$$[1,j]$$$ and right end fixed at $$$i$$$ will have xor-pair less than the value.
Therefore, this becomes a sliding window where we want to maximize the value of the left end $$$j$$$ so that the number of subarrays for a fixed right end $$$i$$$ becomes as large as possible.
To achieve this, we would maintain in our trie the following two things: - the current bit (on/off) - the maximum index which reached this bit in our trie
Now when querying: - if both searched bit and current array index bit is $$$1$$$: take the max for left index from child "on" bit and go to child "off" bit - if both searched bit and current array index bit is $$$0$$$: just go to child "off" bit - if searched bit is $$$1$$$ and current array index bit is $$$0$$$: take the max for left index from child "off" bit and go to child "on" bit - if searched bit is $$$0$$$ and current array index bit is $$$1$$$: just go to child "on" bit
This is done so that we can find the maximum left index for the given fixed right index at $$$i$$$. We follow binary searched value as closely as possible while traversing the trie to stay under the upper bound as well as maximize the left index.
Finally, putting the values and corresponding index in the trie is trivial. Simply follow the trie and put in the corresponding bits the maximum index which can reach that bit.
This way we can solve this problem in $$$O(n \log^2 n)$$$