概要

各区間に含まれる花たちがある日数だけ成長し、最終的に目標の高さに達する花の本数を求める問題です。

考察

この問題では、\(M\) 回の「区間 \([L_j, R_j]\) のすべての花に \(W_j\) だけ成長させる」という操作が行われます。素朴に考えると、毎回の操作で実際に該当する花すべての成長量を足していくと、最悪の場合 \(O(N \cdot M)\) の計算が必要になります。これは制約条件 \(N, M \leq 2 \times 10^5\) のもとでは非常に大きな計算量となり、TLE（時間超過）になってしまいます。

そこで、区間に対する一様な加算を効率的に行う方法として、「いもす法（Imos method; 差分配列）」というテクニックを利用します。この方法では、区間の始点に加算すべき値を足し、終点の次の位置から減算する値を引くことで、区間全体への加算を \(O(1)\) で表現できます。その後、累積和を取ることで各要素に適用された総和を得ることができます。

例えば、花が5本あり、区間 \([2, 4]\) に対して \(3\) の成長を与える場合： - 差分リスト diff に対して： - diff[1] += 3 - diff[4] -= 3 これにより後で累積和を取ると、区間 \([2, 4]\) にだけ \(3\) が反映されます。

このようにして、すべての操作を差分リストに記録し、最後に一度だけ累積和を取り、各花ごとに最終的な高さを計算し、目標の高さ以上かどうか判定すればよいです。

アルゴリズム

1. 各花の初期の高さ \(H_i\) を読み込む。
2. 各花の目標の高さ \(T_i\) を読み込む。
3. 各日の水やり情報を読み込みながら、区間 \([L_j, R_j]\) に成長量 \(W_j\) を加えることを差分リスト diff に記録する：
   • diff[L_j - 1] += W_j
   • diff[R_j] -= W_j（0-indexedに変換しているため）
4. 差分リストの累積和を取り、各花の合計成長量 growth[i] を得る。
5. 各花について、最終的な高さ \(H_i + \text{growth}[i]\) が目標 \(T_i\) 以上かを判定し、カウントする。
6. 条件を満たす花の本数を出力する。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 区間は1-indexedで入力されるので、内部処理では0-indexedに変換する必要がある。
• 差分リストのサイズは \(N+1\) にしておくと、範囲外アクセスを防げる。
• 最終的な成長量は64bit整数型（Pythonでは int）で扱える範囲であることに注意。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    H = [int(data[idx+i]) for i in range(N)]
    idx += N
    T = [int(data[idx+i]) for i in range(N)]
    idx += N
    
    # 区間加算クエリを処理するための差分リスト
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L = int(data[idx]) - 1  # 0-indexed
        idx += 1
        R = int(data[idx]) - 1  # 0-indexed
        idx += 1
        W = int(data[idx])
        idx += 1
        
        diff[L] += W
        diff[R + 1] -= W
    
    # 累積和で各区間の合計成長量を計算
    growth = list(accumulate(diff))[:N]
    
    # 各花の最終的な高さを計算し、目標を超えるか判定
    count = 0
    for i in range(N):
        final_height = H[i] + growth[i]
        if final_height >= T[i]:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。