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

输入 #1

4
1 1048577
1 1
2 2097153
2 3

输出 #1

1048577
-1

说明/提示

限制条件

• $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 翻译