概要

各計画について、区間 \([L_i, R_i]\) の気温の合計を求め、それが閾値 \(K_i\) 以上かどうかを判定する問題です。
区間和を何度も高速に求めるために、累積和 を使うのがポイントです。

考察

この問題では、各クエリごとに

\(A_{L_i} + A_{L_i+1} + \cdots + A_{R_i}\)

を求めて、\(K_i\) と比較すればよいです。

素朴な方法

たとえば各計画ごとに、\(L_i\) から \(R_i\) まで順に足し合わせる方法を考えると、1 回のクエリで最大 \(O(N)\) 時間かかります。
これを \(M\) 回行うと、最悪で \(O(NM)\) になります。

この問題の制約は

• \(N \le 2 \times 10^5\)
• \(M \le 10^5\)

なので、\(O(NM)\) は最大で \(2 \times 10^{10}\) 程度になり、到底間に合いません。

重要な気づき

区間和を何度も求めるなら、あらかじめ 累積和 を作っておくと高速になります。

累積和 prefix を

• prefix[0] = 0
• prefix[i] = A_1 + A_2 + \cdots + A_i

としておくと、区間 \([L, R]\) の和は

\(A_L + A_{L+1} + \cdots + A_R = \text{prefix}[R] - \text{prefix}[L-1]\)

で一瞬で求められます。

具体例

たとえば

\(A = [3, -2, 5, 1, 4]\)

のとき、累積和は

• prefix[0] = 0
• prefix[1] = 3
• prefix[2] = 1
• prefix[3] = 6
• prefix[4] = 7
• prefix[5] = 11

です。

このとき、区間 \([2,4]\) の和は

\(A_2 + A_3 + A_4 = -2 + 5 + 1 = 4\)

ですが、累積和を使えば

\(\text{prefix}[4] - \text{prefix}[1] = 7 - 3 = 4\)

と求められます。

この方法なら、各クエリを \(O(1)\) で処理できます。

アルゴリズム

1. 配列 \(A\) を読み込む。
2. 長さ \(N+1\) の累積和配列 prefix を作る。
   • prefix[0] = 0
   • prefix[i+1] = prefix[i] + A[i]
3. 各クエリ \((L, R, K)\) について、区間和 $\( s = \text{prefix}[R] - \text{prefix}[L-1] \)$ を求める。
4. \(s \ge K\) なら Dangerous、そうでなければ Safe を出力する。

計算量

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

実装のポイント

• クエリの \(L, R\) は 1-indexed なので、累積和もそれに合わせて prefix[0] を用意すると扱いやすいです。

• 区間和は prefix[R] - prefix[L - 1] で求められます。

• \(A_j\) に負の値が含まれていても、累積和はそのまま使えます。

• クエリ数が多いので、Python では sys.stdin.buffer.read() でまとめて高速入力し、出力も配列にためて最後に "\n".join(...) でまとめて行うと安定です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    M = next(it)

    A = [next(it) for _ in range(N)]

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

    out = []
    for _ in range(M):
        L = next(it)
        R = next(it)
        K = next(it)
        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.4-high によって生成されました。