Overview

Each child’s “final number of sweets” uniformly increases by \(q\), and additionally the first \(r\) children each get \(1\) more. This is a problem where we answer range sum queries efficiently using precomputation and simple calculations.

Analysis

First, in this distribution, the number each person receives is: - \(q=\lfloor S/M\rfloor\) (common to everyone) - Additionally, only children \(1 \sim r\) get \(1\) extra (\(r=S\bmod M\))

Therefore, the final count for child \(i\) is [ B_i + q + [i \le r] ] (where \([\,]\) is \(1\) if the condition is true, \(0\) otherwise)

Since the queries ask for “the sum over the interval \([L,R]\)”, naively summing from \(L\) to \(R\) each time would be \(O(NM)\) in the worst case, which is too slow for \(M,N \le 2\times10^5\).

Range sums can be efficiently computed using the classic “prefix sum” technique. Also, \(q\) can be added in one step proportional to the interval length. If we can count “the number of people in the interval with \(i \le r\) who get the extra \(+1\)”, we can process each query in \(O(1)\).

The number of children in the interval \([L,R]\) who receive the extra \(+1\) (children \(1\sim r\)) is: - If \(L>r\), then \(0\) - If \(L\le r\), then the count of people from \(L\) to \(\min(R,r)\), which is [ \min(R,r) - L + 1 ]

Example: When \(M=5, S=12\), we have \(q=2, r=2\).
The extra \(+1\) goes to children \(1,2\) only. In the interval \([2,5]\), the only eligible child is child \(2\), so the count is \(1\).

Algorithm

1. Build the prefix sum of \(B\): \(pref[i]=\sum_{k=1}^{i} B_k\).
2. Compute \(q,r=\mathrm{divmod}(S,M)\).
3. For each query \([L,R]\), compute and output the following:
   • Original sum: [ sum_b = pref[R]-pref[L-1] ]
   • Interval length: [ len = R-L+1 ]
   • Common addition for everyone: \(len \cdot q\)
   • Number of extra \(+1\) recipients:
     • When \(L \le r\): [ extra = \min(R,r)-L+1 ]
     • Otherwise: \(extra=0\)
   • Answer: [ sum_b + len\cdot q + extra ]

Complexity

• Time complexity: Preprocessing \(O(M)\), each query \(O(1)\), so total \(O(M+N)\)
• Space complexity: \(O(M)\) for the prefix sum array, etc.

Implementation Notes

• The answer can involve summing up to \(10^9\)-scale values across \(2\times10^5\) elements, so \(32\)-bit integers will overflow (Python’s int has no such issue).

• When computing extra, pay careful attention to boundaries and always use \(\min(R,r)\) (for the case where \(R<r\)).

• Since the input is large, reading it all at once with sys.stdin.buffer.read() and processing it as a sequence of integers is faster.

  Source Code

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()

This editorial was generated by gpt-5.2-high.