概要

\(N\) 本の街灯があり、それぞれに初期耐久値がある。\(M\) 回の吹雪により、各区間に属する街灯の耐久値が減少する。すべての吹雪が終わった後に、耐久値が 1 以上の街灯の本数を求めよ。

考察

この問題では、単純に各吹雪ごとに区間 \([L_j, R_j]\) の街灯の耐久値を直接減らす処理を行うと、最悪の場合で \(O(N \cdot M)\) の計算量となり、制約 \(N, M \leq 2 \times 10^5\) では間に合いません（TLE します）。

重要な観察は、各街灯に対する吹雪によるダメージの総和だけが必要であり、途中経過は不要だということです。そのため、区間加算を効率的に処理する方法があれば高速化できます。

そこで 差分配列 を使うことを考えます。これは、区間に対して一定の値を加える操作を、配列の始点と終点+1にだけ値を記録することで、\(O(1)\) で処理できる手法です。その後、累積和を取ることで各要素への加算結果を得られます。

例えば、街灯の数 \(N=5\) として、吹雪が区間 \([2, 4]\) に \(D=3\) のダメージを与える場合を考えると：

• 差分配列 diff に対して：
  • diff[1] += 3（0-indexedで2番目）
  • diff[4] -= 3（0-indexedで5番目、ただし存在しないので外側に持っていく）
• 累積和を取ると、区間 \([1, 3]\)（0-indexed）に \(3\) が反映される

このようにして、各吹雪の区間減算を高速に処理し、最後に一度だけ累積和を取って各街灯の総ダメージを計算します。

アルゴリズム

1. 初期の耐久値配列 \(H\) を読み込む。
2. 長さ \(N+1\) の差分配列 diff を用意する（0で初期化）。
3. 各吹雪について：
   • 区間 \([L_j, R_j]\) に \(D_j\) のダメージを加えるために：
     • diff[L_j - 1] += D_j
     • diff[R_j] -= D_j
4. 差分配列の累積和を取り、各街灯へのダメージ合計 damages を得る。
5. 各街灯について、最終耐久値 \(H[i] - damages[i]\) を求め、それが 1 以上ならカウントアップ。
6. カウントした数を出力。

計算量

• 時間計算量: \(O(N + M)\)
  各吹雪の処理が定数時間で終わり、最後に累積和と判定処理が \(O(N)\)。
• 空間計算量: \(O(N)\)
  差分配列とダメージ配列に \(O(N)\) 必要。

実装のポイント

• 吹雪の区間は 1-indexed で与えられるので、配列アクセス時は 0-indexed に変換すること（つまり \(L-1\), \(R\) を使う）。

• 差分配列のサイズは \(N+1\) にしておくことで、右端の更新 diff[R] -= D を安全に行える。

• 最終的に累積和を取る際、diff[:-1] の部分までを使う（最後の余分な要素は除外）。

  ソースコード

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    H = list(map(int, data[idx:idx+N]))
    idx += N
    
    # 差分配列を用意
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L = int(data[idx])
        idx += 1
        R = int(data[idx])
        idx += 1
        D = int(data[idx])
        idx += 1
        
        diff[L-1] += D
        diff[R] -= D
    
    # 累積和で各区間への減少量を求める
    damages = list(accumulate(diff[:-1]))
    
    # 各街灯の最終耐久値を計算し、1以上か判定
    count = 0
    for i in range(N):
        final_health = H[i] - damages[i]
        if final_health >= 1:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。