概要

\(N\) 本の街灯に対して \(M\) 回の吹雪（区間に対する一括減算）が行われた後、耐久値が \(1\) 以上残っている街灯の本数を求める問題です。いもす法を用いることで、区間への加算を効率的に処理できます。

考察

素朴なアプローチとその問題点

最も単純な方法は、各吹雪ごとに街灯 \(L_j\) から \(R_j\) まで1本ずつ耐久値を \(D_j\) 減らすことです。しかし、この方法では1回の吹雪で最大 \(N\) 本の街灯を更新する必要があり、全体で最悪 \(O(N \times M)\) の計算量になります。\(N, M\) がともに最大 \(2 \times 10^5\) なので、\(4 \times 10^{10}\) 回の操作となり、制限時間に間に合いません（TLE）。

重要な気づき

各街灯 \(i\) について最終的に知りたいのは、すべての吹雪によるダメージの合計値 \(\text{damage}[i]\) です。つまり：

\[\text{damage}[i] = \sum_{\substack{j : L_j \leq i \leq R_j}} D_j\]

これが分かれば、\(H_i - \text{damage}[i] \geq 1\) かどうかを判定するだけです。

「区間に一律の値を加算し、最後に各要素の合計を知りたい」という操作は、いもす法（差分配列） で \(O(1)\) ずつ処理できます。

アルゴリズム

いもす法の仕組み

長さ \(N+1\) の差分配列 \(\text{diff}\) を用意します（初期値はすべて \(0\)）。

各吹雪 \((L_j, R_j, D_j)\) に対して： - \(\text{diff}[L_j - 1]\) に \(D_j\) を加算 - \(\text{diff}[R_j]\) から \(D_j\) を減算

具体例: \(N = 5\) で吹雪 \((L=2, R=4, D=3)\) の場合

index	0	1	2	3	4
diff	0	+3	0	0	-3

この差分配列の累積和を取ると：

index	0	1	2	3	4
damage	0	3	3	3	0

街灯 2〜4（0-indexed で 1〜3）にダメージ \(3\) が正しく反映されています。

全体の手順

1. 差分配列 \(\text{diff}\) を用意する
2. \(M\) 回の吹雪それぞれについて、差分配列に \(O(1)\) で記録する
3. 差分配列の累積和を取りながら、各街灯 \(i\) のダメージ合計 \(\text{cumulative}\) を計算する
4. \(H_i - \text{cumulative} \geq 1\) なら倒壊していないのでカウントする
5. 最終的なカウントを出力する

計算量

• 時間計算量: \(O(N + M)\)
  • 差分配列への記録が \(O(M)\)、累積和の計算と判定が \(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列と耐久値配列にそれぞれ \(O(N)\)

実装のポイント

• 1-indexed と 0-indexed の変換: 問題文では街灯は \(1\) から番号が振られていますが、配列は \(0\)-indexed なので、\(L_j - 1\) の位置に加算し、\(R_j\) の位置で減算します。

• オーバーフローに注意: \(D_j\) が最大 \(10^9\) で \(M\) が最大 \(2 \times 10^5\) なので、ダメージ合計は最大 \(2 \times 10^{14}\) 程度になり得ます。Python では整数のオーバーフローがないため問題ありませんが、C++ などでは long long を使う必要があります。

• 高速な入力: \(N, M\) が大きいため、Python では sys.stdin.buffer.read() でまとめて読み込むことで入力を高速化しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    H = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    # imos法で各街灯へのダメージ合計を計算
    diff = [0] * (N + 1)
    for j in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        D = int(input_data[idx]); idx += 1
        diff[L - 1] += D
        diff[R] -= D
    
    count = 0
    cumulative = 0
    for i in range(N):
        cumulative += diff[i]
        if H[i] - cumulative >= 1:
            count += 1
    
    print(count)

main()

---

この解説は claude4.6opus-thinking によって生成されました。