Overview

This problem requires calculating the total tour time for a specified range \([L_j, R_j]\) of areas, given the tour time for each area, and then adding this total to the arrival time \(S_j\) to determine the completion time.

Analysis

The time required for each group to tour areas from \(L_j\) to \(R_j\) is the sum of the tour times for each area: \(\sum_{k=L_j}^{R_j} T_k\). Since the group starts touring from arrival time \(S_j\), the completion time can be expressed as follows:

\[\text{Completion Time} = S_j + \sum_{k=L_j}^{R_j} T_k\]

Naive Approach

For each group (query), one might consider using a loop to sum up \(T_k\) from the \(L_j\)-th to the \(R_j\)-th area. However, this method requires up to \(N\) additions per group. Since the number of groups \(M\) can also be up to \(2 \times 10^5\), the worst-case number of operations is \(N \times M \approx 4 \times 10^{10}\), which will not finish within the time limit (resulting in TLE).

Efficient Approach

Prefix Sum is a highly effective technique for quickly computing “the sum over a specific range.” By precomputing “the total time from area 1 to area \(i\),” the sum over any range \([L, R]\) can be calculated with just a single subtraction.

Algorithm

Building the Prefix Sum

First, prepare an array \(P\) of length \(N+1\). \(P[i]\) stores the total tour time from area 1 to area \(i\). - \(P[0] = 0\) - \(P[1] = T_1\) - \(P[2] = T_1 + T_2 = P[1] + T_2\) - \(P[i] = P[i-1] + T_i\)

By utilizing the previous term in this way, the array \(P\) can be constructed in \(O(N)\) time.

Answering Queries

Using the prefix sum \(P\), the total time for the range \([L_j, R_j]\) can be calculated as follows: $\(\sum_{k=L_j}^{R_j} T_k = P[R_j] - P[L_j - 1]\)\( Using this, the completion time for each group is \)S_j + P[R_j] - P[L_j - 1]\(, and each query can be answered in \)O(1)$ (constant time).

Complexity

• Time Complexity: \(O(N + M)\)
  • Building the prefix sum takes \(O(N)\), and computing the result for each group takes \(O(M)\). Since \(N, M \le 2 \times 10^5\), this is well within the time limit.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array \(P\) that stores the prefix sum.

Implementation Notes

• Fast I/O: Since \(N\) and \(M\) can be large, repeatedly using Python’s standard input() may be slow. It is more efficient to read all input at once using methods such as sys.stdin.read().split().

• Index Adjustment: It is common practice to create the prefix sum array \(P\) with size \(N+1\), with \(0\) at the beginning, to simplify the calculation for range \([L, R]\). This way, to compute the sum starting from area \(L\), you only need to reference \(P[L-1]\).

  Source Code

import sys

def solve():
    # 入力をすべて読み込み、空白で分割してリストにする
    # sys.stdin.read().split() は高速に大量のデータを読み込む際によく使われます
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 読み込んだ文字列を整数のイテレータに変換する
    it = map(int, input_data)
    
    try:
        # エリア数 N とグループ数 M を取得
        N = next(it)
        M = next(it)
        
        # 各エリアの見学時間の累積和を計算する
        # P[i] はエリア 1 からエリア i までの見学時間の合計
        P = [0] * (N + 1)
        for i in range(1, N + 1):
            P[i] = P[i-1] + next(it)
            
        # 各グループの見学完了時刻を計算する
        results = []
        for _ in range(M):
            # 到着時刻 S, 見学範囲の始点 L, 終点 R
            s = next(it)
            l = next(it)
            r = next(it)
            
            # エリア L から R までの見学時間の合計は P[R] - P[L-1]
            # 完了時刻 = 到着時刻 S + 見学時間の合計
            finish_time = s + (P[r] - P[l - 1])
            results.append(str(finish_time))
            
        # 全ての結果を改行で繋いで一度に出力する
        sys.stdout.write('\n'.join(results) + '\n')
    except StopIteration:
        # 入力が制約通りであればここには到達しません
        pass

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.