概要

この問題では、お菓子を特定のルールで子どもたちに分配し、複数の区間について最終的なお菓子の個数の合計を求める必要があります。

考察

まず、分配ルールを整理しましょう。

• お菓子の総数 \(S\) を \(M\) 人で均等に分配します。
• 商 \(q = \left\lfloor \frac{S}{M} \right\rfloor\) が全員に必ずもらえる個数です。
• 余り \(r = S \bmod M\) は、番号の小さい方から \(1\) 個ずつ追加で配られます（つまり、子ども \(1\) から \(r\) までが \(1\) 個多くもらいます）。

したがって、子ども \(i\) が今回もらう個数は以下のように決まります： $\( \begin{cases} q + 1 & \text{if } i \leq r \\ q & \text{if } i > r \end{cases} \)$

最終的な個数は「もともとの個数 \(B_i\)」＋「今回の配布個数」になります。

素朴な方法では？

たとえば、各クエリごとに \(L_j\) から \(R_j\) までの子どもについて、一人ひとり計算して合計するという方法があります。しかし、この方法では最大で \(2 \times 10^5\) 個のクエリ × 最大 \(2 \times 10^5\) 人の子ども = 最悪ケースで \(4 \times 10^{10}\) 回の計算が必要になり、時間内に処理できません（TLE）。

効率的な方法は？

この問題では「区間和」を何度も求めることになるので、累積和を使うのが効果的です。

具体的には、以下の情報を事前に計算しておきます：

• 各子どもが最終的に持っているお菓子の個数を配列として持つ。
• その配列の累積和を取る。

しかし、最終的な個数の配列を直接持つとメモリ的にも時間がかかる可能性があります。そこで、以下のように分解して考えます。

---

任意の区間 \([L, R]\) における合計は次のように求められます：

\[ \sum_{i=L}^{R} (\text{最終的な個数}) = \sum_{i=L}^{R} (B_i + q + \delta_i) \]

ここで、\(\delta_i = 1\) if \(i \leq r\), そうでなければ \(0\)

これを分解すると：

\[ = \underbrace{\sum_{i=L}^{R} B_i}_{\text{(1)}} + \underbrace{(R - L + 1) \cdot q}_{\text{(2)}} + \underbrace{\sum_{i=L}^{R} \delta_i}_{\text{(3)}} \]

それぞれ計算できます：

• (1): \(B\) の累積和を使って高速に計算
• (2): 単純計算
• (3): 区間 \([L, R]\) 内で、\(1\) から \(r\) までの間に含まれる要素の個数 → \(\max(0, \min(R, r) - L + 1)\)

こうすることで、各クエリに \(O(1)\) で応答できるようになります。

アルゴリズム

1. 入力を読み込み、\(q = \left\lfloor \frac{S}{M} \right\rfloor\), \(r = S \bmod M\) を求める。
2. 配列 \(B\) の累積和配列 cum_B を構築する。
3. 各クエリ \((L, R)\) について、上記の3つの項を計算し、合計を求める。
4. 結果を出力。

計算量

• 時間計算量: \(O(M + N)\)
• 空間計算量: \(O(M)\)

実装のポイント

• 累積和の添字に注意（0-indexed vs 1-indexed）

• min(R, r) - L + 1 の計算時に負にならないように max(0, ...) で保護する

• 入力が非常に多いので、高速な入力方法（例：sys.stdin.read）を使用すること

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    
    M = int(data[idx])
    idx += 1
    S = int(data[idx])
    idx += 1
    
    B = [int(data[idx + i]) for i in range(M)]
    idx += M
    
    # q: 各人に配られる基本個数
    # r: 余り（最初のr人に+1個）
    q, r = divmod(S, M)
    
    # 最終的なお菓子の個数の累積和配列を作る
    # 子どもiの最終個数 = B[i] + (q + (1 if i <= r else 0))
    # つまり、B[i] + q + (1 if i <= r else 0)
    # 累積和を取るときに、Bの累積和 + q*(R-L+1) + (rに依存する項)

    # Bの累積和
    cum_B = [0] * (M + 1)
    for i in range(M):
        cum_B[i + 1] = cum_B[i] + B[i]
    
    N = int(data[idx])
    idx += 1
    
    results = []
    for _ in range(N):
        L = int(data[idx])
        idx += 1
        R = int(data[idx])
        idx += 1
        
        # Bの合計
        sum_B = cum_B[R] - cum_B[L - 1]
        
        # qの分：(R - L + 1) * q
        count_q = (R - L + 1) * q
        
        # 余りの分：[L, R] の中で 1..r の範囲にある個数
        # これは min(R, r) - max(L-1, 0) ではなく、min(R, r) - max(L-1, 0)
        # より正確には、[L, R] ∩ [1, r] の個数 = max(0, min(R, r) - max(L-1, 0))
        # ただし L, R は1-indexedなので注意
        # L-1 >= 0 は常に成り立つので max(L-1, 0) = L-1
        # したがって個数は max(0, min(R, r) - (L - 1)) = max(0, min(R, r) - L + 1)
        count_extra = max(0, min(R, r) - L + 1)
        
        total = sum_B + count_q + count_extra
        results.append(total)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。