XOR and Distance
Contest: Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 2900
Tags: bitmasks, divide and conquer, trees

You are given an array $$$a$$$ consisting of $$$n$$$ distinct elements and an integer $$$k$$$. Each element in the array is a non-negative integer not exceeding $$$2^k-1$$$.

Let's define the XOR distance for a number $$$x$$$ as the value of

$$$$$$f(x) = \min\limits_{i = 1}^{n} \min\limits_{j = i + 1}^{n} |(a_i \oplus x) - (a_j \oplus x)|,$$$$$$

where $$$\oplus$$$ denotes the bitwise XOR operation.

For every integer $$$x$$$ from $$$0$$$ to $$$2^k-1$$$, you have to calculate $$$f(x)$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le 19$$$; $$$2 \le n \le 2^k$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2^k-1$$$). All these integers are distinct.

Output format:
Print $$$2^k$$$ integers. The $$$i$$$-th of them should be equal to $$$f(i-1)$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
Consider the first example:

- for $$$x = 0$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[6, 0, 3]$$$, and the minimum absolute difference of two elements is $$$3$$$;
- for $$$x = 1$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[7, 1, 2]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 2$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[4, 2, 1]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 3$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[5, 3, 0]$$$, and the minimum absolute difference of two elements is $$$2$$$;
- for $$$x = 4$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[2, 4, 7]$$$, and the minimum absolute difference of two elements is $$$2$$$;
- for $$$x = 5$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[3, 5, 6]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 6$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[0, 6, 5]$$$, and the minimum absolute difference of two elements is $$$1$$$;
- for $$$x = 7$$$, if we apply bitwise XOR to the elements of the array with $$$x$$$, we get the array $$$[1, 7, 4]$$$, and the minimum absolute difference of two elements is $$$3$$$.

Example input:
3 3
6 0 3

Example output:
3 1 1 2 2 1 1 3

Example input:
3 4
13 4 2

Example output:
2 2 6 6 3 1 2 2 2 2 1 3 6 6 2 2

Editorial:
There are two main approaches to this problem, both of them utilize the same data structure — a trie. But not the usual trie.
We will build a trie with each node storing the following four values. Let the interval represented by a node be $$$[L, R)$$$, then the values are:
• $$$minval$$$ — minimum existing value in the segment relative to $$$L$$$, so, for example, if $$$L = 4$$$ and the minimum number in the segment is $$$5$$$, then $$$minval = 1$$$;
• $$$maxval$$$ — maximum existing value in the segment. Relative to $$$L$$$ as well;
• $$$ans$$$ — the minimum distance between two existing values in the subtree;
• $$$len$$$ — the size of the segment represented by the node.
We build this structure for $$$x = 0$$$, so we just add all the values of the original array into the trie. What happens to this structure when we flip some bit $$$x$$$? Let's say that the bit $$$k-1$$$ is flipped. It means that we have to swap the left child and the right child of the root of the trie. If we flip the bit $$$k-2$$$, we need to swap the neighboring nodes in this trie on depth $$$2$$$, and so on. When we flip the $$$k-i$$$-th bit, it means that we have to rebuild the first $$$i + 1$$$ layers of the trie, which have $$$2^{i+1} - 1$$$ nodes.
So we need to iterate through all possible values of $$$x$$$ while rebuilding the data structure in some way that our rebuilds are not too costly. One of the ways to do it is to use Gray code. If we iterate on $$$x$$$ using a variation of Gray code where we start from most significant bits instead of the least significant bits, the bit $$$k-1$$$ will be swapped $$$2^{k-1}$$$ times (and the total rebuild time for these swaps will be $$$2^{k-1} \cdot 3 < 2^{k+1}$$$), the bit $$$k-2$$$ will be swapped $$$2^{k-2}$$$ times (and the total rebuild time for these swaps will be $$$2^{k-2} \cdot 7 < 2^{k+1}$$$), and so on. So, the total rebuild time for the whole process will be $$$O(2^k \cdot k)$$$.
Brief description of the second approach: for each node, we can store multiple versions of that node. A version of a node is another node which represents the same subtree having all of the numbers XOR'ed by some number $$$x$$$. We can see that if we try to XOR all numbers of a node representing a segment of size $$$4$$$ by, for example, $$$8$$$, nothing changes, and if we try to XOR all numbers by, for example, $$$11$$$, the result for this subtree will be the same as if we XOR it by $$$3$$$. So, for a subtree of size $$$m$$$, we store $$$m$$$ versions of it, so the whole structure contains $$$2^k \cdot k$$$ versions of nodes.