概要

\(N\) 株の花に対して \(M\) 回の範囲更新（水やり）を行い、最終的な水の総量がそれぞれの花の許容限界量 \(S_i\) を超えた株数を数える問題です。

考察

まず、素直にシミュレーションを行う方法を考えてみます。 各水やり作業において、範囲 \([L_j, R_j]\) のすべての花に水量を加算する場合、最悪のケース（すべての作業が全範囲を対象とする場合など）では \(O(N \times M)\) の計算量が必要になります。 今回の制約は \(N, M \le 2 \times 10^5\) であるため、計算回数は最大で \(4 \times 10^{10}\) 回に達し、実行時間制限に間に合いません。

そこで、「範囲への加算」を効率的に行う手法が必要になります。この問題のように、すべての更新が終わった後に最終的な値を参照すればよい形式では、いもす法（差分更新と累積和）を用いるのが最適です。

アルゴリズム

いもす法による効率化

いもす法を用いると、各水やり作業を \(O(1)\) で処理できます。

1. 差分配列の準備: 長さ \(N+2\) の配列 diff を \(0\) で初期化します。
2. 更新処理: 各作業 \((L_j, R_j, W_j)\) に対して、以下の \(2\) 箇所のみを更新します。
   • diff[L_j] += W_j
   • diff[R_j + 1] -= W_j
3. 累積和の計算: すべての作業が終わった後、diff の累積和を計算します。
   • current_total_water = diff[1] + diff[2] + ... + diff[i] この current_total_water が、花 \(i\) が受けた水の総量になります。
4. 判定: 各花 \(i\) について、current_total_water > S_i であれば「根腐れ」としてカウントします。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みに \(O(N + M)\)
  • \(M\) 回の更新処理に \(O(M)\)
  • 累積和の計算と判定に \(O(N)\) 全体で \(O(N + M)\) となり、制約下で十分に高速に動作します。
• 空間計算量: \(O(N)\)
  • 必要水分量 \(S\) と差分配列 diff を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonで \(10^5\) オーダーの入力を処理する場合、input() を繰り返すと時間がかかることがあります。sys.stdin.read().split() を使って一括で読み込むことで、実行時間を大幅に短縮できます。

• インデックスの管理: 問題文は 1-indexed（花 \(1\) 〜 花 \(N\)）ですが、プログラム内での配列の扱いに注意してください。今回は diff 配列を \(N+2\) のサイズで確保することで、1-indexed の範囲 \([L, R]\) に対して diff[L] と diff[R+1] を安全に操作できるようにしています。

• オーバーフロー: Pythonは整数の大きさに制限がないため、合計水量が \(10^{14}\) を超えるようなケース（\(M=2 \times 10^5, W=10^9\)）でも、特別な対策なしで計算可能です。

  ソースコード

import sys

def solve():
    # 全ての入力を一度に読み込み、空白で分割して整数のリストに変換します。
    # これにより、大量の入力を高速に処理できます。
    try:
        input_data = sys.stdin.read().split()
        if not input_data:
            return
        data = list(map(int, input_data))
    except EOFError:
        return

    # N: 花の株数, M: 水やり作業の回数
    N = data[0]
    M = data[1]
    
    # S: 各花の必要水分量（許容限界量）
    # 花 i の限界量は S[i-1] に格納されます。
    S = data[2 : 2 + N]
    
    # いもす法（累積和）のための差分配列を準備します。
    # 花の番号は 1 から N なので、サイズ N + 2 の配列を使用します。
    diff = [0] * (N + 2)
    
    # M 回の水やり作業を処理します。
    # 各作業 j では範囲 [L_j, R_j] に水量 W_j を加えます。
    ptr = 2 + N
    for _ in range(M):
        l = data[ptr]
        r = data[ptr + 1]
        w = data[ptr + 2]
        # 差分配列の更新
        diff[l] += w
        diff[r + 1] -= w
        ptr += 3
        
    rotted_count = 0
    current_total_water = 0
    
    # 差分配列から累積和を計算し、各花が受けた水の総量を求めます。
    for i in range(N):
        # i 番目の花（1-indexed で i+1 番目）の総水量を計算
        current_total_water += diff[i + 1]
        
        # 総水量が許容限界量 S_i を超えているか判定します。
        if current_total_water > S[i]:
            rotted_count += 1
            
    # 「根腐れ」を起こした花の総数を出力します。
    sys.stdout.write(str(rotted_count) + '\n')

if __name__ == '__main__':
    solve()

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