概要

区間 \([L_j, R_j]\) に一括で耐久値を減らす操作が \(M\) 回あるとき、全操作後に耐久値が \(1\) 以上残る街灯の本数を数える問題です。

考察

各吹雪は「ある連続区間の全要素に同じ値 \(D_j\) を加算（ここでは減算）」する操作です。
素朴に、吹雪ごとに区間内の街灯すべてを更新すると、最悪で \(O(NM)\) となり（\(N,M \le 2\times 10^5\) なので最大 \(4\times 10^{10}\) 回程度）、当然間に合いません。

重要な観察は次の通りです。

• 最終的に必要なのは各街灯 \(i\) が受ける減少量の合計 \(\sum D_j\)（ただし \(i \in [L_j, R_j]\) のもの）だけ
• 各吹雪は区間加算なので、「差分配列（いもす法）」で区間加算の累積を高速に処理できる

例えば、区間 \([2,4]\) に \(+3\) したいとき（減少量の合計を作るイメージ）、 - diff[2] に +3 - diff[5] に -3（区間の外に出たら効果を打ち消す） としておき、左から累積和を取ると、ちょうど区間内だけ +3 された配列が復元できます。

この方法なら、各吹雪を \(O(1)\) で反映し、最後に \(O(N)\) で各街灯の総減少量を得られます。

アルゴリズム

1. 入力で初期耐久値配列 \(H\) を受け取る。
2. 長さ \(N+1\) の差分配列 diff を用意する（最終的に累積和を取るため）。
3. 各吹雪 \((L, R, D)\) について以下を行う（\(0\)-indexed に直す）:
   • diff[L-1] += D
   • R < N のとき diff[R] -= D
     （\(R\) が末尾なら打ち消し位置が配列外なので不要）
4. 左から diff の累積和 dec を取りながら、各街灯 \(i\) の最終耐久値を [ H_i - dec ] として計算し、これが \(1\) 以上なら答えに加算する。
5. 数え上げた本数を出力する。

※問題文の通り、途中で倒壊しても減少が止まらないため、「最終的な合計減少量」だけを見れば十分です。

計算量

• 時間計算量: \(O(N + M)\)（吹雪の反映が \(O(M)\)、累積と判定が \(O(N)\)）
• 空間計算量: \(O(N)\)（差分配列 diff と耐久値配列）

実装のポイント

• 差分配列の更新位置に注意：区間 \([L, R]\)（1-indexed）を 0-indexed にすると開始は L-1、終了の打ち消しは R になる。

• diff を 長さ \(N+1\) にしておくと境界処理が安全（本コードでは R < N のときのみ打ち消しを入れている）。

• 減少量や耐久値は最大で \(10^9\)、回数も多いので累積和は大きくなり得るが、Python の int ならオーバーフローしない。

• 高速入出力のために sys.stdin.buffer.read() でまとめて読み取っている。

  ソースコード

import sys

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

    H = [next(it) for _ in range(N)]
    diff = [0] * (N + 1)

    for _ in range(M):
        L = next(it)
        R = next(it)
        D = next(it)
        diff[L - 1] += D
        if R < N:
            diff[R] -= D

    dec = 0
    ans = 0
    for i in range(N):
        dec += diff[i]
        if H[i] - dec >= 1:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

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