概要

この問題は、各エリアの見学時間が与えられたとき、指定された範囲 \([L_j, R_j]\) の見学時間の合計を求め、到着時刻 \(S_j\) に加算した完了時刻を求める問題です。

考察

各グループがエリア \(L_j\) から \(R_j\) までを見学するのにかかる時間は、各エリアの見学時間の和 \(\sum_{k=L_j}^{R_j} T_k\) です。グループは到着時刻 \(S_j\) から見学を開始するため、完了時刻は以下の式で表せます。

\[\text{完了時刻} = S_j + \sum_{k=L_j}^{R_j} T_k\]

素朴なアプローチ

各グループ（クエリ）ごとに、ループを使って \(L_j\) 番目から \(R_j\) 番目までの \(T_k\) を足し合わせる方法が考えられます。しかし、この方法では1つのグループにつき最大で \(N\) 回の加算が必要です。グループの数 \(M\) も最大 \(2 \times 10^5\) であるため、最悪の場合の計算回数は \(N \times M \approx 4 \times 10^{10}\) となり、実行制限時間に間に合いません（TLEとなります）。

効率的なアプローチ

「特定の範囲の合計値」を高速に求める手法として、累積和（Prefix Sum）が非常に有効です。 あらかじめ「1番目から \(i\) 番目までのエリアの合計時間」を計算しておけば、どのような範囲 \([L, R]\) の合計も、引き算ひとつで計算できるようになります。

アルゴリズム

累積和の構築

まず、長さ \(N+1\) の配列 \(P\) を用意します。\(P[i]\) にはエリア 1 から \(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\)

このように、前の項を利用することで、配列 \(P\) は \(O(N)\) の時間で作成できます。

クエリへの回答

累積和 \(P\) を使うと、範囲 \([L_j, R_j]\) の合計時間は以下のように計算できます。 $\(\sum_{k=L_j}^{R_j} T_k = P[R_j] - P[L_j - 1]\)\( これを利用すれば、各グループの完了時刻は \)S_j + P[R_j] - P[L_j - 1]\( となり、各クエリに対して \)O(1)$（定数時間）で回答できます。

計算量

• 時間計算量: \(O(N + M)\)
  • 累積和の構築に \(O(N)\)、各グループの計算に \(O(M)\) かかります。\(N, M \le 2 \times 10^5\) なので、制限時間内に十分間に合います。
• 空間計算量: \(O(N)\)
  • 累積和を保持するための配列 \(P\) に \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) や \(M\) が大きいため、Pythonの標準的な input() を繰り返すと時間がかかる場合があります。sys.stdin.read().split() などを用いて一括で入力を読み込むのが効率的です。

• インデックスの調整: 累積和の配列 \(P\) は、範囲 \([L, R]\) の計算を簡略化するために、先頭に \(0\) を入れたサイズ \(N+1\) で作成するのが一般的です。これにより、エリア \(L\) からの合計を求める際に \(P[L-1]\) を参照するだけでよくなります。

  ソースコード

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

---

この解説は gemini-3-flash-preview によって生成されました。