概要

各計画ごとに「区間 \([L, R]\) の気温合計」が閾値 \(K\) 以上かどうかを判定する問題です。
多数の区間和クエリを高速に処理するために、累積和（prefix sum） を使います。

考察

この問題の本質は、クエリごとに [ AL + A{L+1} + \cdots + A_R ] を素早く求めることです。

素朴な方法

各クエリで \(L\) から \(R\) までを毎回足し合わせると、1クエリあたり最悪 \(O(N)\) かかります。
クエリ数は最大 \(M=10^5\) なので、全体では最悪 \(O(NM)\)（約 \(2\times 10^{10}\)）となり、時間内に終わりません（TLE）。

重要な気づき

区間和は累積和を使うと一瞬で求められます。

累積和配列 prefix を [ \text{prefix}[i] = A_1 + A_2 + \cdots + A_i ] （ただし prefix[0]=0）とすると、 [ A_L + \cdots + A_R = \text{prefix}[R] - \text{prefix}[L-1] ] で求められます。

これなら各クエリは \(O(1)\) で判定可能です。

例えば \(A=[3,-2,5,1]\) のとき、
prefix=[0,3,1,6,7]。
区間 \([2,4]\) の和は [ \text{prefix}[4]-\text{prefix}[1]=7-3=4 ] となります。

アルゴリズム

1. 入力を受け取る。
2. 長さ \(N+1\) の累積和配列 prefix を作る（prefix[0]=0）。
3. i=1..N について prefix[i] = prefix[i-1] + A[i]（実装では0-index配列に合わせて調整）。
4. 各クエリ \((L, R, K)\) について
   • s = prefix[R] - prefix[L-1] を計算
   • s >= K なら Dangerous、そうでなければ Safe を出力配列に追加
5. 最後にまとめて出力する。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• L, R は 1-indexed で与えられるため、累積和の式 prefix[R] - prefix[L-1] がそのまま使えるように、prefix を長さ N+1 で作るのが安全です。

• 値に負数が含まれても累積和は問題なく使えます。

• Python では高速化のため sys.stdin.readline、出力はリストにためて "\n".join(...) でまとめて行うと良いです。

  ソースコード

import sys

def main():
    input = sys.stdin.readline

    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]

    out = []
    for _ in range(M):
        L, R, K = map(int, input().split())
        s = prefix[R] - prefix[L - 1]
        out.append("Dangerous" if s >= K else "Safe")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

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