/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
N = 2^{20} 項からなる数列 A = (A_0, A_1, \dots, A_{N - 1}) があります。はじめ、全ての要素は -1 です。
Q 個のクエリを順番に処理してください。i \, (1 \leq i \leq Q) 個目のクエリは t_i = 1 または t_i = 2 を満たす整数 t_i および整数 x_i で表され、内容は以下の通りです。
- t_i = 1 のとき、以下の処理を順番に行う。
- 整数 h を h = x_i で定める。
- A_{h \bmod N} \neq -1 である間、h の値を 1 増やすことを繰り返す。この問題の制約下でこの操作が有限回で終了することは証明できる。
- A_{h \bmod N} の値を x_i で書き換える。
- t_i = 2 のとき、その時点での A_{x_i \bmod N} の値を出力する。
なお、整数 a, b に対し、a を b で割った余りを a \bmod 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)
- t_i = 2 であるような i \, (1 \leq i \leq Q) が 1 つ以上存在する。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
Q
t_1 x_1
\vdots
t_{Q} x_{Q}
出力
t_i = 2 であるようなクエリに対し、それぞれ答えを 1 行に出力せよ。そのようなクエリが 1 つ以上存在することは保証される。
入力例 1
4 1 1048577 1 1 2 2097153 2 3
出力例 1
1048577 -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 は定数であり、入力では与えられないことに注意してください。
Score : 400 points
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.
- Define an integer h as h = x_i.
- 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.
- 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.