分数: 400 点
问题陈述
有一个序列 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 or t_i = 2,和另一个整数 x_i,如下。
- If t_i = 1,按顺序执行以下操作。
- 定义一个整数 h as h = x_i.
- 虽然 A_{h \bmod N} \neq -1,继续添加 1 to h。我们可以证明,在该问题的约束下,该过程在有限迭代后结束。
- 替换值 A_{h \bmod N} 与 x_i.
- If 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,所以我们添加 1 to h。现在我们有 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 是一个常量,未在输入中给出。