P14947 Minpopcount

Rikka has a set $S$ containing elements in $[0, 2^k)$, which is initially empty. Then $q$ events will happen, each of which is one of the following two types: 1. Given an integer $x \in [0, 2^k)$, insert $x$ into $S$. It is guaranteed that $x$ is not in $S$ before this operation. 2. Given an integer $x \in [0, 2^k)$. For all $y \in S$, compute the minimum value of $\operatorname{popcount}(x \oplus y)$. It is guaranteed that $S$ is non-empty before this operation. Please help Rikka solve this problem by outputting the correct answer for every type $2$ event.

The first line contains two integers $q$ and $k$ ($1 \leq q \leq 5\cdot 10^6$, $1 \leq k \leq 20$), representing the number of events and the size of the value range. The next $q$ lines each contain two integers $o$ and $x$ ($o \in \{1, 2\}$, $0 \leq x < 2^k$), describing an event, where $o$ is the event type and $x$ is the event parameter.

For each type $2$ event, output one line with one integer representing the answer.

For the first sample, when the first query happens, $x = 5$ and $S = \{2, 3\}$. We have $\operatorname{popcount}(5 \oplus 2) = 3$ and $\operatorname{popcount}(5 \oplus 3) = 2$, so the answer to the query is $2$. The second query happens when $x = 6$ and $S = \{2, 3, 4\}$. We have $\operatorname{popcount}(6 \oplus 2) = 1$, $\operatorname{popcount}(6 \oplus 3) = 2$, and $\operatorname{popcount}(6 \oplus 4) = 1$, so the answer to the query is $1$. Translated by ChatGPT 5