分数: 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,回答以下问题:
- 查找桶中的水量 B_i 紧随其后 T_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
我们将解释第一个查询。
最初,桶 3 由人持有 3.
紧接着 1-st 操作,铲斗 3 由人持有 2 并包含 3 水单位。
紧接着 2-nd 操作,铲斗 3 由人持有 4 并包含 5 水单位。
紧接着 3-rd 操作,铲斗 3 由人持有 2 并包含 9 水单位。
紧接着 4第次操作,桶 3 由人持有 4 并包含 11 水单位。
因此,第一个查询的答案是 11.