B - Distribution of Sweets Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は M 人の子どもたちにお菓子を配ることになりました。子どもたちにはそれぞれ 1 から M までの番号が付けられています。お菓子は全部で S 個あります。

各子ども i（1 \leq i \leq M）は、分配の前からすでに B_i 個のお菓子を持っています。

分配のルールは以下の通りです：

  • S を M で割った商を q = \lfloor S / M \rfloor、余りを r = S \mod M とする。
  • すべての子どもに q 個ずつ配る。
  • さらに、余った r 個のお菓子を、番号の小さい子どもから順に 1 個ずつ追加で配る。すなわち、子ども 1, 2, \ldots, r にそれぞれ追加で 1 個ずつ配る（r = 0 の場合、追加の配布は行わない）。

以上により、子ども i が今回の分配でもらうお菓子の個数は、i \leq r ならば q + 1 個、i > r ならば q 個です。

子ども i の 最終的なお菓子の個数 を、もともと持っていた B_i 個と今回もらった個数の合計と定めます。

高橋君は、青木君からの N 個の質問に答えなければなりません。j 番目の質問（1 \leq j \leq N）では、子ども 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
  • 1 行目には、子どもの人数 M と、お菓子の総数 S がスペース区切りで与えられる。
  • 2 行目には、各子どもがもともと持っているお菓子の個数 B_1, B_2, \ldots, B_M がスペース区切りで与えられる。
  • 3 行目には、質問の数 N が与えられる。
  • 続く N 行のうち j 行目（1 \leq j \leq N）には、j 番目の質問の範囲を表す L_j と R_j がスペース区切りで与えられる。これは子ども L_j から子ども R_j まで（両端を含む）を意味する。

出力

N 行出力せよ。j 行目（1 \leq j \leq N）には、j 番目の質問に対する答え、すなわち子ども 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

Score : 333 pts

Problem Statement

Takahashi is going to distribute sweets to M children. The children are numbered from 1 to M. There are S sweets in total.

Each child i (1 \leq i \leq M) already has B_i sweets before the distribution.

The rules of distribution are as follows:

  • Let q = \lfloor S / M \rfloor be the quotient and r = S \mod M be the remainder when S is divided by M.
  • Give q sweets to every child.
  • Additionally, distribute the remaining r sweets one by one to the children in order of their numbers, starting from the smallest. That is, children 1, 2, \ldots, r each receive one additional sweet (if r = 0, no additional distribution is performed).

As a result, the number of sweets child i receives in this distribution is q + 1 if i \leq r, and q if i > r.

The final number of sweets for child i is defined as the sum of the B_i sweets they originally had and the number they received in this distribution.

Takahashi must answer N questions from Aoki. For the j-th question (1 \leq j \leq N), find the sum of the final number of sweets for children from child L_j to child R_j (inclusive).

Output the answer for each of the N questions.

Constraints

  • 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)
  • All inputs are integers.

Input

M S
B_1 B_2 \ldots B_M
N
L_1 R_1
L_2 R_2
\vdots
L_N R_N
  • The first line contains the number of children M and the total number of sweets S, separated by a space.
  • The second line contains the number of sweets each child originally has, B_1, B_2, \ldots, B_M, separated by spaces.
  • The third line contains the number of questions N.
  • In the following N lines, the j-th line (1 \leq j \leq N) contains L_j and R_j separated by a space, representing the range of the j-th question. This means from child L_j to child R_j (inclusive).

Output

Output N lines. The j-th line (1 \leq j \leq N) should contain the answer to the j-th question, that is, the sum of the final number of sweets for children from child L_j to child R_j.

Note that the answer may not fit within the range of a 32-bit integer.

Sample Input 1

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

Sample Output 1

28
17
15

Sample Input 2

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

Sample Output 2

30
5
25

Sample Input 3

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

Sample Output 3

385
14
265
113
272

Sample Input 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

Sample Output 4

11000000000
1100000000
5500000000
5500000000
5500000000
1100000000

Sample Input 5

1 1000000000
1000000000
1
1 1

Sample Output 5

2000000000