概要

区間に対する値の加算（ダメージの蓄積）を複数回行った後、各要素の最終的な状態を判定する問題です。

考察

各吹雪について、指定された範囲 \(L_j\) から \(R_j\) までの街灯の耐久値を \(D_j\) ずつ減らしていくという操作を行います。

素朴なアプローチとして、吹雪が来るたびに \(L_j\) から \(R_j\) までの街灯すべてに対してループを回してダメージを計算する方法が考えられます。しかしこの場合、1回の吹雪で最大 \(N\) 本の街灯に影響が出るため、全体の計算量は \(O(N \times M)\) となります。制約が \(N, M \le 2 \times 10^5\) であるため、最悪ケースでは計算回数が \(4 \times 10^{10}\) 回に達し、実行時間制限（TLE）に引っかかってしまいます。

すべての吹雪が終わった後の「各街灯が受けた合計ダメージ」を高速に求める必要があります。このように「特定の区間に同じ値を足す」という操作を複数回行う場合、「いもす法（差分と累積和）」を使うのが非常に効果的です。

アルゴリズム

「いもす法」を用いて、各街灯が受ける合計ダメージを計算します。

1. 長さ \(N+2\) の差分配列 diff を用意し、すべて \(0\) で初期化します。
2. \(j\) 回目の吹雪（区間 \([L_j, R_j]\) にダメージ \(D_j\)）について、以下の操作を行います。
   • diff[L_j] に \(D_j\) を足す（ここからダメージが始まる）
   • diff[R_j + 1] から \(D_j\) を引く（ここからダメージが終わる）

具体例：街灯2から4の範囲に5のダメージを与える場合、diff[2] に \(5\) を足し、diff[5] から \(5\) を引きます。後で累積和をとると、インデックス1, 2, 3, 4, 5 の値はそれぞれ \(0, 5, 5, 5, 0\) となり、正しく区間全体にダメージが加算される仕組みです。

1. すべての吹雪の情報を記録した後、配列 diff の累積和をとります。左から順に current_damage += diff[i] と計算していくと、current_damage が街灯 \(i\) の受けた合計ダメージになります。
2. 最後に、各街灯の初期耐久値 \(H_i\) と合計ダメージを比較し、\(H_i > current_damage\) であれば倒壊していない（耐久値が \(1\) 以上残っている）街灯として答えに \(1\) を加算します。

計算量

• 時間計算量: \(O(N + M)\) 差分配列への記録に \(O(M)\)、累積和の計算と生き残りの判定に \(O(N)\) かかるため、全体の計算量は \(O(N + M)\) となります。これは制約下でも十分に高速に動作します。
• 空間計算量: \(O(N)\) 初期耐久値の配列と、長さ \(N+2\) の差分配列 diff を保持するためのメモリが必要です。

実装のポイント

• 1-indexed（1始まり）の扱い: 問題文のインデックスは \(1\) から始まります。配列のサイズを \(N+2\) に確保しておくことで、diff[R+1] にアクセスする際に配列外参照（IndexError）が起きるのを防いでいます。

• 高速な入出力: Pythonでは標準入力の読み込みがボトルネックになりやすいため、sys.stdin.read().split() を用いて入力全体を一度に読み込み、後からパースする手法をとることで実行時間を大幅に短縮しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    H = [int(x) for x in input_data[2:N+2]]
    
    diff = [0] * (N + 2)
    
    idx = N + 2
    for _ in range(M):
        L = int(input_data[idx])
        R = int(input_data[idx+1])
        D = int(input_data[idx+2])
        diff[L] += D
        diff[R+1] -= D
        idx += 3
        
    current_damage = 0
    ans = 0
    for i in range(1, N + 1):
        current_damage += diff[i]
        if H[i-1] > current_damage:
            ans += 1
            
    print(ans)

if __name__ == '__main__':
    main()

---

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