概要

各子どもの「最終的なお菓子の個数」は一様に \(q\) 個増え、さらに先頭 \(r\) 人だけが追加で \(1\) 個増えるので、区間和クエリを前計算と簡単な計算で高速に答える問題です。

考察

まず、今回の分配で全員が受け取る個数は - \(q=\lfloor S/M\rfloor\) 個（全員共通） - さらに子ども \(1 \sim r\) だけが追加で \(1\) 個（\(r=S\bmod M\)）

したがって子ども \(i\) の最終個数は [ B_i + q + [i \le r] ] （\([\,]\) は条件が真なら \(1\)、偽なら \(0\)）

ここで質問は「区間 \([L,R]\) の合計」なので、素朴に毎回 \(L\) から \(R\) まで足し上げると最悪で \(O(NM)\) になり、\(M,N \le 2\times10^5\) では間に合いません。

区間和は典型的に「累積和（prefix sum）」で高速化できます。また、\(q\) は区間長に比例して一発で足せます。残る「\(i \le r\) の分だけ増える人数」を数えられれば、各クエリを \(O(1)\) で処理できます。

区間 \([L,R]\) に含まれる「追加 \(+1\) をもらう子（\(1\sim r\)）」の人数は、 - もし \(L>r\) なら \(0\) - もし \(L\le r\) なら、\(L\sim \min(R,r)\) の人数なので [ \min(R,r) - L + 1 ] となります。

例：\(M=5, S=12\) のとき \(q=2, r=2\)。
追加 \(+1\) は子ども \(1,2\) のみ。区間 \([2,5]\) では追加対象は子ども \(2\) だけなので人数は \(1\)。

アルゴリズム

1. \(B\) の累積和 \(pref[i]=\sum_{k=1}^{i} B_k\) を作る。
2. \(q,r=\mathrm{divmod}(S,M)\) を計算する。
3. 各クエリ \([L,R]\) について以下を計算して出力する：
   • もともとの合計：[ sum_b = pref[R]-pref[L-1] ]
   • 区間長：[ len = R-L+1 ]
   • 全員共通の加算：\(len \cdot q\)
   • 追加 \(+1\) の人数：
     • \(L \le r\) のとき [ extra = \min(R,r)-L+1 ]
     • それ以外は \(extra=0\)
   • 答え：[ sum_b + len\cdot q + extra ]

計算量

• 時間計算量: 前処理 \(O(M)\)、各クエリ \(O(1)\) なので合計 \(O(M+N)\)
• 空間計算量: 累積和配列などで \(O(M)\)

実装のポイント

• 答えは最大で \(10^9\) 級の値が \(2\times10^5\) 個分足される可能性があるため、\(32\) ビット整数では溢れます（Python の int は問題なし）。

• extra の計算は境界に注意し、必ず \(\min(R,r)\) を使います（\(R<r\) のケース）。

• 入力が大きいので sys.stdin.buffer.read() でまとめて読み、整数列として処理すると高速です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    M = next(it)
    S = next(it)

    B = [0] * (M + 1)
    pref = [0] * (M + 1)
    for i in range(1, M + 1):
        B[i] = next(it)
        pref[i] = pref[i - 1] + B[i]

    q, r = divmod(S, M)

    N = next(it)
    out = []
    for _ in range(N):
        L = next(it)
        R = next(it)
        sum_b = pref[R] - pref[L - 1]
        length = R - L + 1
        extra = 0
        if L <= r:
            extra = min(R, r) - L + 1
        out.append(str(sum_b + length * q + extra))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。