← 返回题目列表

AtCoder · abc228_d

G. 线性探测

中文机器翻译题面 查看原题

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