Overview

This problem asks you to distribute \(S\) candies among \(M\) children according to the rules, then find the total number of candies held by children in specified intervals. By using prefix sums, each query can be answered in \(O(1)\).

Analysis

First, the final number of candies each child \(i\) holds can be easily calculated.

• Let \(q = \lfloor S / M \rfloor\) and \(r = S \mod M\). Then the number of candies child \(i\) receives this time is \(q + 1\) if \(i \leq r\), and \(q\) if \(i > r\).
• Therefore, the final number of candies is \(B_i + q + [i \leq r]\) (where \([i \leq r]\) is \(1\) if the condition is true, \(0\) otherwise).

Problem with the naive approach: If we naively sum from \(L_j\) to \(R_j\) for each query, a single query takes up to \(O(M)\), resulting in \(O(NM)\) overall. Since both \(N\) and \(M\) can be up to \(2 \times 10^5\), this would require up to \(4 \times 10^{10}\) operations in the worst case, causing TLE.

Solution: Since we want to compute interval sums efficiently, we use prefix sums. By precomputing the prefix sums of each child’s final candy count, we can answer any interval \([L, R]\) sum in \(O(1)\).

Algorithm

1. Compute \(q = \lfloor S / M \rfloor\) and \(r = S \mod M\).
2. Build the prefix sum array \(\text{prefix}[0..M]\):
   • \(\text{prefix}[0] = 0\)
   • \(\text{prefix}[i] = \text{prefix}[i-1] + B_i + q + [i \leq r]\) (\(i = 1, 2, \ldots, M\))
3. For each query \((L_j, R_j)\), the answer is \(\text{prefix}[R_j] - \text{prefix}[L_j - 1]\).

Concrete example: For \(M = 3\), \(S = 7\), \(B = [2, 5, 3]\)

• \(q = 2\), \(r = 1\), so the distribution amounts are \([3, 2, 2]\)
• Final candy counts: \([2+3, 5+2, 3+2] = [5, 7, 5]\)
• Prefix sums: \([0, 5, 12, 17]\)
• Query \((2, 3)\) → \(\text{prefix}[3] - \text{prefix}[1] = 17 - 5 = 12\)

Complexity

• Time complexity: \(O(M + N)\)
  • \(O(M)\) to build the prefix sums, and \(O(1)\) × \(N\) queries gives \(O(N)\)
• Space complexity: \(O(M + N)\)
  • \(O(M)\) for the prefix sum array, \(O(N)\) for the output buffer

Implementation Notes

• Caution with 64-bit integers: Since \(B_i\) can be up to \(10^9\) and \(q\) can also be around \(10^9\), interval sums may exceed \(2 \times 10^{14}\). In C++ and similar languages, you need to use long long. In Python, there is no integer overflow, so this is handled automatically.

• Fast I/O: Since \(N\) and \(M\) can be as large as \(2 \times 10^5\), in Python we use sys.stdin.readline for input and sys.stdout.write for batch output to avoid TLE.

• 1-indexed vs 0-indexed conversion: Children are 1-indexed while array \(B\) is 0-indexed, so be careful to access elements using B[i-1].

  Source Code

import sys
input = sys.stdin.readline

def main():
    M, S = map(int, input().split())
    B = list(map(int, input().split()))
    
    q, r = divmod(S, M)
    
    # Build prefix sum of final candy counts
    # Child i (1-indexed): final = B[i-1] + q + (1 if i <= r else 0)
    prefix = [0] * (M + 1)
    for i in range(1, M + 1):
        extra = 1 if i <= r else 0
        prefix[i] = prefix[i - 1] + B[i - 1] + q + extra
    
    N = int(input())
    out = []
    for _ in range(N):
        L, R = map(int, input().split())
        out.append(str(prefix[R] - prefix[L - 1]))
    
    sys.stdout.write('\n'.join(out) + '\n')

main()

This editorial was generated by claude4.6opus-thinking.