← 返回题目列表

AtCoder · abc438_e

H. 重型铲斗

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

分数: 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.