概要

本問題は、一列に並んだ \(N\) 株の花に対して \(M\) 回の区間水やり（乾燥度の減少）を行った後、最終的な乾燥度が閾値 \(T\) 以下となる花の株数を求める問題です。 「乾燥度は \(0\) 未満にならない」という制約を数式で整理し、いもす法（差分配列）を用いることで、時間制限内に高速に解くことができます。

考察

1. 愚直なシミュレーションの限界

各水やり作業において、指定された区間 \([L_j, R_j]\) の要素を一つずつ更新していく素朴な方法を考えます。 この場合、1回の水やりで最大 \(N\) 回の要素更新が発生するため、全体の計算量は \(O(NM)\) となります。 本問題の制約は \(N \leq 5 \times 10^5\)、\(M \leq 2 \times 10^5\) であるため、最悪の場合に \(10^{11}\) 回程度の計算が必要となり、実行時間制限に間に合いません（TLE）。

2. 「乾燥度が \(0\) 未満にならない」という制約の言い換え

問題文には「乾燥度は \(0\) 未満にならない」とあります。一見すると、水やりのたびに各花の乾燥度が \(0\) に達したかどうかを判定・処理しなければならないように見えます。

しかし、最終的な状態だけに注目すると、この制約は非常にシンプルに言い換えることができます。 花 \(i\) に対する \(M\) 回の水やりによる減少量の総和を \(S_i\) とします。 途中で乾燥度が \(0\) 未満にならないように制限されることを考慮すると、最終的な乾燥度は \(\max(F_i - S_i, 0)\) と表せます。

私たちが知りたいのは、最終的な乾燥度が \(T\) 以下になる（\(\max(F_i - S_i, 0) \leq T\)）かどうかです。 \(T \geq 0\) であるため、この不等式は以下のように変形できます。

\[ \max(F_i - S_i, 0) \leq T \iff F_i - S_i \leq T \iff S_i \geq F_i - T \]

つまり、途中の各ステップで「\(0\) 未満になったか」を逐一管理する必要はなく、「最終的な総減少量 \(S_i\) が \(F_i - T\) 以上であるか」だけを判定すればよいことになります。

3. いもす法による区間加算の高速化

問題は「各クエリ \((L_j, R_j, D_j)\) について、区間 \([L_j, R_j]\) に一律に \(D_j\) を加算し、最終的な各位置の総和 \(S_i\) を求める」という問題に帰着されました。 これはいもす法（差分配列）を用いることで、クエリあたり \(O(1)\)、全体で \(O(N + M)\) の計算量で処理できます。

アルゴリズム

1. 差分配列の用意: 長さ \(N+2\) の配列 diff を \(0\) で初期化します。

2. クエリの処理（いもす法）: 各水やりクエリ \((L_j, R_j, D_j)\) に対して、以下の加算を行います。

   • diff[L_j] += D_j
   • diff[R_j + 1] -= D_j

3. 累積和の計算と判定: 配列 diff の累積和を左から順に計算していくことで、各花 \(i\) の総減少量 \(S_i\) を復元します。 \(i = 1, 2, \ldots, N\) について順に以下を行います。

   • \(S_i = S_{i-1} + \text{diff}[i]\)
   • \(S_i \geq F_i - T\) を満たすならば、その花は「元気な状態」になるため、答えのカウントを \(1\) 増やします。

計算量

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

  • \(M\) 回のクエリ処理に \(O(M)\) 時間かかります。
  • 累積和の計算と条件判定に \(O(N)\) 時間かかります。
  • 全体として \(O(N + M)\) となり、実行時間制限に余裕で間に合います。

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

  • 初期乾燥度を保持する配列 \(F\) と、差分配列 diff のために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonでは入力の行数が多くなると input() の呼び出し回数が増えて実行時間が長くなります。sys.stdin.read().split() を使用して入力を一括で取得し、メモリ上でパースすることで大幅に高速化できます。

• 1-indexed の扱い: 花の番号が \(1\) から始まるため、配列のサイズを \(N+2\) にし、初期乾燥度配列 \(F\) の先頭にダミーの要素（0）を挿入することで、インデックスのズレによるバグを防いでいます。

  ソースコード

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])
    T = int(input_data[2])

    F = [0] + [int(x) for x in input_data[3 : 3 + N]]

    diff = [0] * (N + 2)
    idx = 3 + N
    for _ in range(M):
        L = int(input_data[idx])
        R = int(input_data[idx + 1])
        D = int(input_data[idx + 2])
        diff[L] += D
        diff[R + 1] -= D
        idx += 3

    ans = 0
    current = 0
    for i in range(1, N + 1):
        current += diff[i]
        if current >= F[i] - T:
            ans += 1

    print(ans)


if __name__ == "__main__":
    solve()

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