102283: [AtCoder]ABC228 D - Linear Probing

Problem Statement

There is a sequence $A = (A_0, A_1, \dots, A_{N - 1})$ with $N = 2^{20}$ terms. Initially, every term is $-1$.

Process $Q$ queries in order. The $i$-th query $(1 \leq i \leq Q)$ is described by an integer $t_i$ such that $t_i = 1$ or $t_i = 2$, and another integer $x_i$, as follows.

• If $t_i = 1$, do the following in order.
  1. Define an integer $h$ as $h = x_i$.
  2. While $A_{h \bmod N} \neq -1$, keep adding $1$ to $h$. We can prove that this process ends after finite iterations under the Constraints of this problem.
  3. Replace the value of $A_{h \bmod N}$ with $x_i$.
• If $t_i = 2$, print the value of $A_{x_i \bmod N}$ at that time.

Here, for integers $a$ and $b$, $a \bmod b$ denotes the remainder when $a$ is divided by $b$.

Constraints

• $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)$
• There is at least one $i$ $(1 \leq i \leq Q)$ such that $t_i = 2$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$Q$
$t_1$ $x_1$
$\vdots$
$t_{Q}$ $x_{Q}$

Output

For each query with $t_i = 2$, print the response in one line. It is guaranteed that there is at least one such query.

Sample Input 1

4
1 1048577
1 1
2 2097153
2 3

Sample Output 1

1048577
-1

We have $x_1 \bmod N = 1$, so the first query sets $A_1 = 1048577$.

In the second query, initially we have $h = x_2$, for which $A_{h \bmod N} = A_{1} \neq -1$, so we add $1$ to $h$. Now we have $A_{h \bmod N} = A_{2} = -1$, so this query sets $A_2 = 1$.

In the third query, we print $A_{x_3 \bmod N} = A_{1} = 1048577$.

In the fourth query, we print $A_{x_4 \bmod N} = A_{3} = -1$.

Note that, in this problem, $N = 2^{20} = 1048576$ is a constant and not given in input.

问题描述

有一个序列$A = (A_0, A_1, \dots, A_{N - 1})$，其中$N = 2^{20}$项。初始时，每一项都为$-1$。

按顺序处理$Q$个查询。第$i$个查询$(1 \leq i \leq Q)$由整数$t_i$表示，其中$t_i = 1$或$t_i = 2$，以及另一个整数$x_i$，如下所示。

• 如果$t_i = 1$，按顺序执行以下操作。
  1. 将整数$h$定义为$h = x_i$。
  2. 当$A_{h \bmod N} \neq -1$时，一直向$h$添加$1$。我们可以在本问题的约束条件下证明这个过程在有限次迭代后结束。
  3. 将$A_{h \bmod N}$的值替换为$x_i$。
• 如果$t_i = 2$，打印那时$A_{x_i \bmod N}$的值。

对于整数$a$和$b$，$a \bmod b$表示$a$除以$b$的余数。

约束条件

• $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)$
• 至少有一个$i$$(1 \leq i \leq Q)$，使得$t_i = 2$。
• 输入中的所有值都是整数。

输入

输入格式如下：从标准输入中给出输入：

$Q$
$t_1$ $x_1$
$\vdots$
$t_{Q}$ $x_{Q}$

输出

对于每个查询$t_i = 2$，在一行中打印响应。我们保证至少有一个这样的查询。

样例输入1

4
1 1048577
1 1
2 2097153
2 3

样例输出1

1048577
-1

我们有$x_1 \bmod N = 1$，所以第一个查询将$A_1 = 1048577$。

在第二个查询中，初始时我们有$h = x_2$，其中$A_{h \bmod N} = A_{1} \neq -1$，所以我们向$h$添加$1$。现在我们有$A_{h \bmod N} = A_{2} = -1$，所以这个查询将$A_2 = 1$。

在第三个查询中，我们打印$A_{x_3 \bmod N} = A_{1} = 1048577$。

在第四个查询中，我们打印$A_{x_4 \bmod N} = A_{3} = -1$。

注意，在本问题中，$N = 2^{20} = 1048576$是一个常数，不作为输入给出。