概要

各グループが見学する区間 \([L_j, R_j]\) の所要時間の合計を求め、到着時刻 \(S_j\) に足すだけの問題です。区間和を高速に求めるために累積和を使います。

考察

各エリアは同時に複数グループが見学でき、待ち時間が発生しないので、グループ同士の干渉は一切ありません。したがって、グループ \(j\) の終了時刻は

• 「到着時刻」 \(S_j\)
• 「エリア \(L_j\) から \(R_j\) までの見学時間の合計」 \(\sum_{i=L_j}^{R_j} T_i\)

の和になります。

素朴に各クエリごとに \(\sum_{i=L_j}^{R_j} T_i\) をループで足すと、1クエリあたり最悪 \(O(N)\)、全体で最悪 \(O(NM)\) となり、\(N, M \le 2\times 10^5\) では間に合いません。

そこで、\(T\) の累積和を前計算しておけば、任意の区間和を \(O(1)\) で求められます。

例： \(T = [3,1,4,1,5]\) のとき累積和 \(pref\) を - \(pref[0]=0\) - \(pref[i]=T_1+\cdots+T_i\) とすると、区間 \([2,4]\) の和は \(pref[4]-pref[1]=(3+1+4+1)-(3)=6\) のように一瞬で求まります。

アルゴリズム

1. 長さ \(N\) の配列 \(T\) を受け取る。
2. 累積和配列 \(pref\)（長さ \(N+1\)）を作る。
   • \(pref[0]=0\)
   • \(pref[i]=pref[i-1]+T_i\)（\(i=1..N\)）
3. 各グループ \((S,L,R)\) について
   • 区間和 \(sum = pref[R]-pref[L-1]\)
   • 終了時刻 \(ans = S + sum\) を出力する。

計算量

• 時間計算量: 累積和構築が \(O(N)\)、各クエリが \(O(1)\) なので全体で \(O(N+M)\)
• 空間計算量: 累積和配列に \(O(N)\)

実装のポイント

• \(pref\) を \(N+1\) 要素で用意し、\(pref[0]=0\) とすることで、区間和を常に \(pref[R]-pref[L-1]\) の形で統一できます（\(L=1\) のときも自然に処理可能）。

• \(T_i\) や累積和、答えは最大で \(10^9 \times 2\times 10^5\) 程度になりうるため、言語によっては 64bit 整数が必要です（Python は自動で多倍長なので問題なし）。

• 入力が大きいので、Python では sys.stdin.readline を使うと安全です。

  ソースコード

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

この解説は gpt-5.2-high によって生成されました。