Score : $400$ points

问题描述

存在一个包含 $N = 2^{20}$ 项的序列 $A = (A_0, A_1, \dots, A_{N - 1})$。最初，每个项的值均为 $-1$。

按照顺序处理 $Q$ 个查询请求。第 $i$（$1 \leq i \leq Q$）个查询由一个整数 $t_i$ 和另一个整数 $x_i$ 描述，其中 $t_i$ 可以为 $1$ 或 $2$，具体如下：

• 若 $t_i = 1$，按以下顺序执行操作：
  1. 定义一个整数 $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$ 后的余数。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 09:58:52