概要

各街灯の初期耐久値から、複数の吹雪による範囲減少分を合計した後、耐久値が1以上残っている街灯の本数を求める問題です。

考察

素朴なアプローチでは、各吹雪に対して街灯の範囲 \([L_j, R_j]\) の各要素から \(D_j\) を減算すると、\(O(NM)\) の時間がかかり、制約条件 \(N, M \leq 2 \times 10^5\) では実行時間がかかりすぎます。

そこで、効率的に範囲加算（減算）を行うために、いもす法（累積和の応用）を使用します。各吹雪の情報を差分配列に記録し、最後に累積和を計算することで、各街灯の総減少量を \(O(N+M)\) で求めることができます。

アルゴリズム

1. 長さ \(N+1\) の差分配列 diff を0で初期化します。
2. 各吹雪 \((L_j, R_j, D_j)\) について:
   • diff[L_j] += D_j
   • diff[R_j+1] -= D_j
3. 差分配列の累積和を計算しながら、各街灯 \(i\) の総減少量 total_reduction を求めます。
4. 初期耐久値 \(H_i\) が総減少量 total_reduction より大きい街灯の個数を数えます。

計算量

• 時間計算量: \(O(N + M)\)
  • 吹雪の情報を読み取る処理が \(O(M)\)
  • 累積和の計算とカウントが \(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列と耐久値配列の保持に \(O(N)\)

実装のポイント

• 配列のインデックスは0始まりなので、入力の \(L_j\), \(R_j\) から1を引いて調整します。

• 差分配列のサイズは \(N+1\) とし、R_j+1 のインデックスが範囲外にならないようにします。

• 累積和を計算する変数 total_reduction を適切に更新しながら、各街灯の条件判定を行います。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    m = int(data[1])
    H = list(map(int, data[2:2+n]))
    events = []
    index = 2 + n
    for i in range(m):
        l = int(data[index])
        r = int(data[index+1])
        d = int(data[index+2])
        index += 3
        events.append((l-1, r-1, d))
    
    diff = [0] * (n+1)
    for l, r, d in events:
        diff[l] += d
        diff[r+1] -= d
        
    total_reduction = 0
    count = 0
    for i in range(n):
        total_reduction += diff[i]
        if H[i] > total_reduction:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。