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