概要

\(N\) 本の花に対して、\(M\) 回の「区間加算（特定の範囲の成長）」を行い、最終的な高さがそれぞれの目標値 \(T_i\) 以上になった花の本数を数える問題です。

考察

素朴な方法とその限界

まず思いつくのは、各日の水やりごとに、指定された範囲 \([L_j, R_j]\) の花一本一本の高さを更新する方法です。 しかし、この方法では \(1\) 回の水やりで最大 \(N\) 本の更新が発生するため、全体の計算量は \(O(N \times M)\) となります。 本問題の制約は \(N, M \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限（通常 2 秒程度）を大幅に超えてしまいます。

効率的な更新の工夫

今回の問題では、「すべての水やりが終わった後の最終的な高さ」だけが重要です。途中の高さを逐一確認する必要はありません。 このように、複数の区間加算をまとめて最後に行う場合に非常に有効なのが「いもす法（差分配列）」という手法です。

アルゴリズム

いもす法（差分配列）

いもす法を用いると、区間 \([L, R]\) に値 \(W\) を加える操作を、配列の端の 2 箇所を更新するだけで済ませることができます。

1. 長さ \(N+1\) の差分配列 diff を用意し、すべて \(0\) で初期化します。
2. 各日の水やり \((L_j, R_j, W_j)\) に対して、以下のように更新します：
   • diff[L_j - 1] += W_j （区間の始まりに加算）
   • diff[R_j] -= W_j （区間の終わりの次に減算）
3. すべての水やりが終わった後、diff の前から順に累積和をとります。
   • current_growth = diff[0] + diff[1] + ... + diff[i] とすると、この current_growth が花 \(i+1\) の最終的な合計成長量になります。
4. 各花について「初期の高さ \(H_i\) + 合計成長量 \(\geq\) 目標の高さ \(T_i\)」を判定し、条件を満たすものをカウントします。

この手法により、各水やりの処理は \(O(1)\) で終わり、最後の集計も \(O(N)\) で済むため、劇的に高速化されます。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みに \(O(N + M)\)
  • \(M\) 回の水やり処理（いもす法）に \(O(M)\)
  • 累積和による最終的な高さの計算と判定に \(O(N)\)
• 空間計算量: \(O(N + M)\)
  • 花の情報や水やりの情報を保持するための配列に \(O(N + M)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Python の場合、input() を繰り返すと時間がかかるため、sys.stdin.read().split() などで一括で読み込むのが定石です。

• インデックスの調整: 問題文は 1-indexed（1番目から始まる）ですが、プログラムの配列は通常 0-indexed（0番目から始まる）です。L-1 や R の扱いに注意が必要です。

• 数値の大きさ: 目標の高さ \(T_i\) が最大 \(10^{18}\) に達するため、成長量の合計も大きな値になります。Python は標準で多倍長整数を扱えるため、オーバーフローの心配はありません。

  ソースコード

import sys

# 競技プログラミング用の高速な入出力とアルゴリズム
def solve():
    # 全ての入力を一度に読み込み、空白で分割してリストにする
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 全ての文字列を整数に一括変換する（ループ内で変換するより高速）
    all_ints = list(map(int, input_data))
    
    # N: 花の本数, M: 水やりの日数
    N = all_ints[0]
    M = all_ints[1]
    
    # H: 各花の初期の高さ
    # T: 各花の目標の高さ
    # スライスを用いてリストを抽出
    H = all_ints[2 : N + 2]
    T = all_ints[N + 2 : 2 * N + 2]
    
    # いもす法（差分配列）を用いて区間加算を効率的に行う
    # diff[i] は i 番目の花からの成長量の変化を表す
    # 花の番号は 1 から N なので、0-indexed に直してサイズ N+1 の配列を用意
    diff = [0] * (N + 1)
    
    # 水やり情報の開始インデックス
    start_idx = 2 * N + 2
    # M 日間の水やりを処理
    for j in range(M):
        # 各日の情報: L (左端), R (右端), W (伸びる高さ)
        idx = start_idx + 3 * j
        L = all_ints[idx]
        R = all_ints[idx + 1]
        W = all_ints[idx + 2]
        
        # 1-indexed の区間 [L, R] を 0-indexed に変換して差分配列を更新
        diff[L - 1] += W
        diff[R] -= W
        
    # 十分に成長した花の本数をカウント
    count = 0
    current_growth = 0
    # 差分配列の累積和をとることで、各花の最終的な合計成長量を求める
    for i in range(N):
        current_growth += diff[i]
        # 最終的な高さ = 初期高さ + 合計成長量
        # これが目標高さ T[i] 以上であればカウント
        if H[i] + current_growth >= T[i]:
            count += 1
            
    # 結果を出力
    sys.stdout.write(str(count) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。