Overview

This problem requires computing the total time for each group to visit their interval \([L_j, R_j]\), then adding it to their arrival time \(S_j\). We use prefix sums to efficiently compute interval sums.

Analysis

Since multiple groups can visit an area simultaneously and no waiting time occurs, there is no interference between groups. Therefore, the finishing time for group \(j\) is the sum of:

• The “arrival time” \(S_j\)
• The “total viewing time from area \(L_j\) to \(R_j\)”: \(\sum_{i=L_j}^{R_j} T_i\)

If we naively compute \(\sum_{i=L_j}^{R_j} T_i\) with a loop for each query, it takes \(O(N)\) per query and \(O(NM)\) overall in the worst case, which is too slow for \(N, M \le 2\times 10^5\).

Instead, by precomputing the prefix sums of \(T\), we can answer any interval sum query in \(O(1)\).

Example: For \(T = [3,1,4,1,5]\), define the prefix sum array \(pref\) as: - \(pref[0]=0\) - \(pref[i]=T_1+\cdots+T_i\)

Then the sum over interval \([2,4]\) is: \(pref[4]-pref[1]=(3+1+4+1)-(3)=6\) which can be computed instantly.

Algorithm

1. Read the array \(T\) of length \(N\).
2. Build the prefix sum array \(pref\) (of length \(N+1\)).
   • \(pref[0]=0\)
   • \(pref[i]=pref[i-1]+T_i\) (\(i=1..N\))
3. For each group \((S,L,R)\):
   • Compute the interval sum \(sum = pref[R]-pref[L-1]\)
   • Output the finishing time \(ans = S + sum\)

Complexity

• Time complexity: Building the prefix sums takes \(O(N)\), and each query takes \(O(1)\), so the overall complexity is \(O(N+M)\).
• Space complexity: \(O(N)\) for the prefix sum array.

Implementation Notes

• By preparing \(pref\) with \(N+1\) elements and setting \(pref[0]=0\), the interval sum can always be uniformly expressed as \(pref[R]-pref[L-1]\) (this naturally handles the case \(L=1\) as well).

• The values of \(T_i\), prefix sums, and answers can be as large as \(10^9 \times 2\times 10^5\), so depending on the language, 64-bit integers may be required (Python handles this automatically with arbitrary precision integers, so there is no issue).

• Since the input can be large, in Python it is safer to use sys.stdin.readline.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    T = list(map(int, input().split()))
    pref = [0] * (N + 1)
    for i, x in enumerate(T, 1):
        pref[i] = pref[i - 1] + x

    out = []
    for _ in range(M):
        S, L, R = map(int, input().split())
        out.append(str(S + (pref[R] - pref[L - 1])))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.