← 返回题目列表

AtCoder · awc0040_b

B. 糖果分发

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

分数: 333 分

问题陈述

高桥要给大家分发糖果 M 孩子们。孩子们的编号是从 总共 1 to M。有 S 糖果。

每个孩子 i (1 \leq i \leq M) 已经有 B_i 分发前的糖果。

分配规则如下:

  • 让 q = \lfloor S / M \rfloor 是商并且 r = S \mod M 为余数 S 除以 M.
  • 给 q 给每个孩子糖果。
  • 另外,分发剩余的 r 糖果按照数量的顺序,从最小的开始,一颗一颗地给孩子们。也就是说,孩子们 1, 2, \ldots, r 每人额外获得一份糖果(如果 r = 0,不执行额外分发)。

结果,糖果的数量 i 在此分发中收到的是 q + 1 if i \leq r,和 q if i > r.

的 树的 最终糖果数量 儿童用 i 定义为 B_i 他们最初拥有的糖果以及他们在此分发中收到的数量。

高桥必须回答 N 青木的问题。对于 j第一个问题(1 \leq j \leq N), 从 child 中求出孩子们最终的糖果数量之和 L_j 给孩子 R_j (含)。

输出每个的答案 N 问题。

约束

  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq S \leq 10^{9}
  • 0 \leq B_i \leq 10^{9} (1 \leq i \leq M)
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L_j \leq R_j \leq M (1 \leq j \leq N)
  • 所有输入均为整数。

输入

M S
B_1 B_2 \ldots B_M
N
L_1 R_1
L_2 R_2
\vdots
L_N R_N
  • 第一行包含孩子的数量 M 和糖果总数 S,用空格分隔。
  • 第二行包含每个孩子原来拥有的糖果数量, B_1, B_2, \ldots, B_M,用空格分隔。
  • 第三行包含问题数量 N.
  • 在下面 N 行, j- 第行 (1 \leq j \leq N) 包含 L_j 和 R_j 以空格分隔,代表范围 j- 第一个问题。这意味着从孩子 L_j 给孩子 R_j (含)。

输出

输出 N 行。的 j- 第行 (1 \leq j \leq N)应包含以下问题的答案 j第题,即从child开始给孩子的糖果最终数量之和 L_j 给孩子 R_j.

请注意,答案可能不适合 32 位整数的范围。


示例输入 1

5 13
1 2 3 4 5
3
1 5
2 4
1 3

示例输出 1

28
17
15

示例输入 2

3 0
5 10 15
3
1 3
1 1
2 3

示例输出 2

30
5
25

示例输入 3

8 25
10 20 30 40 50 60 70 80
5
1 8
1 1
3 7
1 4
5 8

示例输出 3

385
14
265
113
272

示例输入 4

10 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
6
1 10
1 1
1 5
6 10
3 7
10 10

示例输出 4

11000000000
1100000000
5500000000
5500000000
5500000000
1100000000

示例输入 5

1 1000000000
1000000000
1
1 1

示例输出 5

2000000000