/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 475 点
問題文
N 人の人がおり、N 個のバケツがあります。人とバケツにはそれぞれ 1, 2, \ldots, N の番号が付けられています。
人 i ははじめバケツ i のみを持っており、バケツ i には何も入っていません。
これから、以下の操作を 10^9 回行います。
- i = 1, 2, \ldots, N について同時に、人 i が持っているバケツすべてに水を i ずつ入れ、それらのバケツを人 A_i に渡す。
ただし、バケツに入れることのできる水の量に制限はありません。
i = 1, 2, \ldots, Q について以下の形式のクエリに答えてください。
- T_i 回目の操作の直後にバケツ B_i に入っている水の量を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 1 \leq T_i \leq 10^9
- 1 \leq B_i \leq N
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N Q A_1 A_2 \ldots A_N T_1 B_1 T_2 B_2 \vdots T_Q B_Q
出力
Q 行出力せよ。i 行目には i 番目のクエリに対する答えを出力せよ。
入力例 1
5 6 3 4 2 2 5 4 3 6 5 1 4 10 1 10 2 1000000000 1
出力例 1
11 30 4 28 30 2999999998
1 番目のクエリに対する説明を行います。
はじめ、バケツ 3 は人 3 が持っています。
1 回目の操作の直後、バケツ 3 は人 2 が持っており、水が 3 入っています。
2 回目の操作の直後、バケツ 3 は人 4 が持っており、水が 5 入っています。
3 回目の操作の直後、バケツ 3 は人 2 が持っており、水が 9 入っています。
4 回目の操作の直後、バケツ 3 は人 4 が持っており、水が 11 入っています。
したがって、1 番目のクエリに対する答えは 11 となります。
Score : 475 points
Problem Statement
There are N people and N buckets. Both the people and buckets are numbered 1, 2, \ldots, N.
Initially, person i holds only bucket i, and bucket i is empty.
From now on, the following operation will be performed 10^9 times:
- For i = 1, 2, \ldots, N simultaneously, person i adds i units of water to each of the buckets they are holding and passes those buckets to person A_i.
Here, there is no limit on the amount of water that can be put in a bucket.
For i = 1, 2, \ldots, Q, answer the following queries:
- Find the amount of water in bucket B_i immediately after the T_i-th operation.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 1 \leq T_i \leq 10^9
- 1 \leq B_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q A_1 A_2 \ldots A_N T_1 B_1 T_2 B_2 \vdots T_Q B_Q
Output
Output Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
5 6 3 4 2 2 5 4 3 6 5 1 4 10 1 10 2 1000000000 1
Sample Output 1
11 30 4 28 30 2999999998
We will explain the first query.
Initially, bucket 3 is held by person 3.
Immediately after the 1-st operation, bucket 3 is held by person 2 and contains 3 units of water.
Immediately after the 2-nd operation, bucket 3 is held by person 4 and contains 5 units of water.
Immediately after the 3-rd operation, bucket 3 is held by person 2 and contains 9 units of water.
Immediately after the 4-th operation, bucket 3 is held by person 4 and contains 11 units of water.
Thus, the answer to the first query is 11.