概要

\(N\) 本の花に対して \(M\) 回の区間一様加算を行い、最終的な高さが目標以上になった花の本数を数える問題です。いもす法（差分配列） を使って区間加算を効率的に処理します。

考察

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

最も単純な方法は、各水やり操作 \(j\) に対して、花 \(L_j\) から \(R_j\) まで1本ずつ高さを \(W_j\) 加算することです。しかし、この方法では1回の水やりで最大 \(N\) 本の花を更新する必要があり、全体で \(O(N \times M)\) の計算量になります。\(N, M\) がともに最大 \(2 \times 10^5\) なので、最悪 \(4 \times 10^{10}\) 回の操作となり、TLE（実行時間超過） になります。

重要な気づき

各水やり操作は「区間 \([L_j, R_j]\) に一律 \(W_j\) を加算する」という形をしています。このような区間一様加算を大量に行い、最後にまとめて各位置の値を求めたい場合、いもす法（差分配列） が非常に有効です。

アルゴリズム

いもす法（差分配列）の仕組み

サイズ \(N+1\) の差分配列 diff を用意し、すべて \(0\) で初期化します。

区間 \([L, R]\) に \(W\) を加算したいとき、次の2つの操作だけを行います：

• diff[L] += W（区間の始まりで加算開始）
• diff[R+1] -= W（区間の終わりの次で加算終了）

具体例: \(N = 5\) で区間 \([2, 4]\) に \(W = 3\) を加算する場合

diff: [0, 0, 0, 0, 0, 0]  (インデックス 0〜5)
操作後: [0, +3, 0, 0, -3, 0]  (diff[1] += 3, diff[4] -= 3)  ※0-indexed

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

累積和: [0, 3, 3, 3, 0, 0]

インデックス 1〜3（花2〜花4）にちょうど \(3\) が加算されていることが分かります。

全体の流れ

1. 差分配列 diff を用意する
2. \(M\) 回の水やり操作をそれぞれ差分配列に \(O(1)\) で記録する
3. 差分配列の累積和を取りながら、花 \(i\) の最終的な高さ \(H_i + \text{累積和}_i\) を計算する
4. \(H_i + \text{累積和}_i \geq T_i\) となる花の本数を数える

計算量

• 時間計算量: \(O(N + M)\)
  • 差分配列への記録: \(M\) 回の操作それぞれ \(O(1)\) で \(O(M)\)
  • 累積和の計算と判定: \(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列、初期高さ、目標高さの配列にそれぞれ \(O(N)\)

実装のポイント

• 1-indexed と 0-indexed の変換: 問題では花の番号が \(1\) から始まるため、差分配列を 0-indexed で管理する場合は diff[L-1] += W、diff[R] -= W とする（コード中ではこの方式を採用）。

• オーバーフローへの注意: \(W_j\) は最大 \(10^9\)、操作回数は最大 \(2 \times 10^5\) 回なので、累積和は最大約 \(2 \times 10^{14}\) に達し得ます。また \(T_i\) は最大 \(10^{18}\) です。Python は整数のオーバーフローがないため心配不要ですが、C++ などでは long long を使う必要があります。

• 高速な入力: \(N, M\) が大きいため、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
    T = [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
        W = int(input_data[idx]); idx += 1
        diff[L - 1] += W
        if R < N:
            diff[R] -= W
    
    count = 0
    cumsum = 0
    for i in range(N):
        cumsum += diff[i]
        if H[i] + cumsum >= T[i]:
            count += 1
    
    print(count)

main()

---

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