AT_abc228_d [ABC228D] Linear Probing

有一个长度为 $N = 2^{20}$ 的数列 $A = (A_0, A_1, \dots, A_{N-1})$。初始时，所有元素均为 $-1$。 请依次处理 $Q$ 个查询。第 $i$ 个查询由整数 $t_i$（$t_i = 1$ 或 $t_i = 2$）和整数 $x_i$ 给出，具体内容如下： - 当 $t_i = 1$ 时，依次进行以下操作： 1. 令整数 $h = x_i$。 2. 当 $A_{h \bmod N} \neq -1$ 时，不断将 $h$ 的值加 $1$。在本题的约束下，可以证明此操作会在有限次内结束。 3. 用 $x_i$ 替换 $A_{h \bmod N}$ 的值。 - 当 $t_i = 2$ 时，输出当前 $A_{x_i \bmod N}$ 的值。 其中，对于整数 $a, b$，$a \bmod b$ 表示 $a$ 除以 $b$ 的余数。

输入按以下格式从标准输入给出。 > $Q$ > $t_1\ x_1$ > $\vdots$ > $t_Q\ x_Q$

对于每个 $t_i = 2$ 的查询，依次输出答案，每个答案占一行。保证至少存在一个 $t_i = 2$ 的查询。

### 限制条件 - $1 \leq Q \leq 2 \times 10^5$ - $t_i \in \{1, 2\}$（$1 \leq i \leq Q$） - $0 \leq x_i \leq 10^{18}$（$1 \leq i \leq Q$） - 至少存在一个 $t_i = 2$ 的查询。 - 输入均为整数。 ### 样例解释 1 由于 $x_1 \bmod N = 1$，所以第 1 个查询后 $A_1 = 1048577$。 第 2 个查询时，初始 $h = x_2$，但 $A_{h \bmod N} = A_1 \neq -1$，因此 $h$ 增加 $1$，此时 $A_{h \bmod N} = A_2 = -1$，所以本次查询后 $A_2 = 1$。 第 3 个查询时，输出 $A_{x_3 \bmod N} = A_1 = 1048577$。 第 4 个查询时，输出 $A_{x_4 \bmod N} = A_3 = -1$。 注意，本题中 $N = 2^{20} = 1048576$ 是常数，输入中不会给出。 由 ChatGPT 4.1 翻译