概要

\(N\) 個の地点の気温が与えられたとき、指定された区間 \([L_i, R_i]\) の気温の合計（熱負荷）が閾値 \(K_i\) 以上であるかどうかを \(M\) 個のクエリに対して判定する問題です。

考察

もっとも単純な方法は、各クエリごとに \(L_i\) から \(R_i\) までループを回して気温を足し合わせることです。しかし、この方法では 1 つのクエリにつき最大で \(N\) 回の加算が必要になります。クエリの数は \(M\) 個あるため、最悪の場合の計算量は \(O(N \times M)\) となります。

本問題の制約は \(N \leq 2 \times 10^5, M \leq 10^5\) であるため、最悪ケースでは \(2 \times 10^{10}\) 回程度の計算が必要になり、実行制限時間に間に合いません（一般に 1 秒間に処理できる計算量は \(10^8\) 回程度です）。

そこで、累積和という手法を用いることで、どのような区間の和であっても \(O(1)\)（定数時間）で計算できるように工夫します。

アルゴリズム

累積和の利用

まず、最初の地点から各地点までの気温の合計をあらかじめ計算しておきます。 これを累積和配列 \(S\) と呼び、以下のように定義します。 - \(S[0] = 0\) - \(S[i] = A_1 + A_2 + \cdots + A_i\) （\(1 \leq i \leq N\)）

このとき、\(S[i]\) は \(S[i-1] + A_i\) という式で順番に求めることができます。

一度この配列 \(S\) を作ってしまえば、任意の区間 \([L, R]\) の和は以下の計算だけで求められます。 $\(\sum_{j=L}^{R} A_j = S[R] - S[L-1]\)$

具体例

例えば、気温が \(A = [3, 1, 4, 1, 5]\) のとき、累積和は \(S = [0, 3, 4, 8, 9, 14]\) となります。 2番目から4番目までの和（\(1+4+1=6\)）を求めたい場合、 \(S[4] - S[2-1] = S[4] - S[1] = 9 - 3 = 6\) となり、正しく計算できていることがわかります。

計算量

• 時間計算量: \(O(N + M)\)
  • 累積和の構築に \(O(N)\)、各クエリの処理に \(O(1)\) かかるため、全体で \(O(N + M)\) となります。これは制約下で十分に高速です。
• 空間計算量: \(O(N)\)
  • 長さ \(N+1\) の累積和配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Python の場合、input() や print() を大量に繰り返すと入出力がボトルネックになることがあります。sys.stdin.read().split() で一括で読み込み、sys.stdout.write() で一括で出力することで実行時間を短縮できます。

• インデックスの扱い: 問題文では地点が 1-based（1番目から始まる）で与えられます。累積和配列 \(S\) を \(N+1\) のサイズで作成し、\(S[0]=0\) としておくことで、1-based のクエリ \(L, R\) に対して \(S[R] - S[L-1]\) と直感的に記述できます。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込み、空白で分割してリストにする（高速化のため）
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用して各要素を順番に取得する
    it = iter(input_data)
    
    # 地点の数 N と 計画の数 M を取得
    N = int(next(it))
    M = int(next(it))
    
    # 累積和を格納する配列 S を用意する
    # S[i] は 1 番目から i 番目までの地点の気温の合計を保持する
    S = [0] * (N + 1)
    current_total = 0
    for i in range(1, N + 1):
        current_total += int(next(it))
        S[i] = current_total
        
    # 各計画（クエリ）を処理する
    results = []
    for _ in range(M):
        L = int(next(it))
        R = int(next(it))
        K = int(next(it))
        
        # 区間 [L, R] の気温の合計は累積和の差 S[R] - S[L-1] で求められる
        heat_load = S[R] - S[L-1]
        
        # 熱負荷が閾値 K 以上であれば Dangerous、そうでなければ Safe
        if heat_load >= K:
            results.append("Dangerous")
        else:
            results.append("Safe")
            
    # 全ての結果を改行で連結して一気に出力する（高速化のため）
    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()

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