概要

各花に複数回にわたって水やりを行い、最終的な高さが目標以上になった花の本数を求める問題です。

考察

各花 \(i\) の最終的な高さは、初期高さ \(H_i\) に「その花が水やりを受けた日の \(W_j\) の合計」を加えたものです。素朴な方法では、各花について全ての水やり操作をチェックすると \(O(N \times M)\) 時間かかり、制約が大きい（\(N, M \leq 200,000\)）ため実行時間制限に間に合いません。そこで、効率的に各区間加算を処理する手法が必要です。

アルゴリズム

この問題は「区間加算」と「最後の値の取得」に帰着できます。効率的に処理するために、いもす法（累積和の応用） を使用します。

1. 長さ \(n+1\) の配列 diff を用意します（0-indexed）。
2. 各水やり操作 \((L_j, R_j, W_j)\) に対して:
   • diff[L_j] += W_j
   • diff[R_j+1] -= W_j
3. 配列 diff の累積和を計算すると、各位置 \(i\) の値が花 \(i\) が受けた水やりの合計量（\(total\_water\)）になります。
4. 各花 \(i\) について、最終高さ \(H_i + total\_water\) が目標 \(T_i\) 以上かどうかをチェックし、条件を満たす花の本数を数えます。

計算量

• 時間計算量: \(O(N + M)\)
  • 水やり操作の処理に \(O(M)\)
  • 累積和の計算と花のチェックに \(O(N)\)
• 空間計算量: \(O(N)\)
  • 配列 diff のサイズが \(n+1\)

実装のポイント

• 入力の花の番号は1-indexedなので、配列アクセス時には0-indexedに変換（\(-1\)）する必要があります。

• 配列 diff はサイズ \(n+1\) で確保し、R+1 のインデックスが範囲外にならないように注意します。

• 累積和を計算しながら同時に花の条件チェックを行うことで、余分なループを避けています。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    H = [int(next(it)) for _ in range(n)]
    T = [int(next(it)) for _ in range(n)]
    queries = []
    for _ in range(m):
        L = int(next(it)); R = int(next(it)); W = int(next(it))
        queries.append((L-1, R-1, W))
    
    diff = [0] * (n+1)
    for L, R, W in queries:
        diff[L] += W
        diff[R+1] -= W
    
    total_water = 0
    count = 0
    for i in range(n):
        total_water += diff[i]
        final_height = H[i] + total_water
        if final_height >= T[i]:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

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