概要

複数の区間に対して値を減算する操作を何度も行った後、最終的な値が特定の閾値以下になる要素の個数を求める問題です。一見すると複雑な条件がありますが、問題の性質を整理することで、いもす法（累積和）を用いた \(O(N + M)\) の高速なアルゴリズムに帰着できます。

考察

素朴なアプローチとその限界

各水やりクエリごとに、指定された区間 \([L_j, R_j]\) のすべての花に対して乾燥度を更新していく方法が考えられます。 しかし、この方法では 1 回の水やりにつき最大で \(O(N)\) の計算量がかかり、全体で \(O(NM)\) の時間がかかってしまいます。 本問題では \(N \le 5 \times 10^5\)、\(M \le 2 \times 10^5\) であるため、全体で約 \(10^{11}\) 回の計算が必要となり、実行時間制限（TLE）になってしまいます。

高速化のために、区間加算（減算）を効率的に行う手法を考える必要があります。

重要な考察：「乾燥度が \(0\) 未満にならない」ルールの単純化

問題文には「乾燥度は \(0\) 未満にならない（\(\max(v - D_j, 0)\) に更新される）」というルールがあります。一見すると、このルールのために「各ステップで値が \(0\) になったかどうか」を愚直に管理しなければならないように思えます。

しかし、最終的な目標は「最終的な乾燥度が \(T\) 以下であるか」を判定することです。 ある花 \(i\) に対する、すべての水やりによる減少量の総和を \(S_i\) とします。このとき、途中の下限 \(0\) のクリップを完全に無視して、単に \(S_i \ge F_i - T\) であるかどうかを判定するだけで正しい結果が得られます。

なぜなら、閾値 \(T\) は非負（\(T \ge 0\)）であるため、以下の 2 つのケースに分けて考えることができます。

1. \(S_i \ge F_i - T\) のとき

   • もし水やりの途中で乾燥度が \(0\) に達した場合、最終的な乾燥度は \(0\) になります。\(T \ge 0\) より、最終的な乾燥度 \(0\) は \(T\) 以下となります。
   • 水やりの途中で一度も \(0\) に達しなかった場合、最終的な乾燥度は正確に \(F_i - S_i\) となり、これは \(T\) 以下です。
   • したがって、どちらの場合も最終的な乾燥度は \(T\) 以下になります。

2. \(S_i < F_i - T\) のとき

   • \(T \ge 0\) より \(S_i < F_i\) となります。総減少量が初期値未満であるため、乾燥度が途中で \(0\) に達することは絶対にありません。
   • したがって、最終的な乾燥度は正確に \(F_i - S_i\) となり、これは \(T\) より大きくなります。

この考察により、「途中で \(0\) 未満にならない」という複雑な制約を気にする必要はなく、「各花 \(i\) に対する減少量の総和 \(S_i\) が \(F_i - T\) 以上であるか」を判定するだけでよいことが分かります。

区間加算の高速化（いもす法）

「複数の区間 \([L_j, R_j]\) に値 \(D_j\) を加算し、最終的な各位置の総和を求める」という処理は、いもす法（差分配列）を用いることで非常に高速に行うことができます。

長さ \(N+2\) の差分配列 diff を用意し、各クエリ \((L_j, R_j, D_j)\) に対して、 - diff[L_j] += D_j - diff[R_j + 1] -= D_j

という操作を \(O(1)\) で行います。すべてのクエリを処理した後に、左から累積和をとることで、各花 \(i\) に対する総減少量 \(S_i\) を \(O(N)\) で一挙に求めることができます。

アルゴリズム

1. 長さ \(N+2\) の差分配列 diff を \(0\) で初期化します。
2. 各クエリ \((L_j, R_j, D_j)\) について、diff[L_j] += D_j および diff[R_j + 1] -= D_j を行います。
3. 差分配列の累積和を左から順に計算します。現在位置 \(i\) での累積和（＝花 \(i\) の総減少量 \(S_i\)）を求めます。
4. \(S_i \ge F_i - T\) を満たしていれば、その花は「元気な状態」になるため、答えのカウントを \(1\) 増やします。
5. 最終的なカウントを出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • クエリの処理に \(O(M)\)、累積和の計算と条件判定に \(O(N)\) かかります。全体として線形時間で動作するため、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N)\)
  • 初期乾燥度を保持する配列 \(F\) と、差分配列 diff を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• オーバーフローの防止 乾燥度の初期値 \(F_i\) や減少量 \(D_j\) は最大で \(10^9\) であり、累積和 \(S_i\) は最大で \(M \times \max(D_j) = 2 \times 10^{14}\) に達します。 32ビット整数型（int）ではオーバーフローしてしまうため、累積和を保持する変数や差分配列には必ず 64ビット整数型（C++ では long long）を使用してください。

• 配列の境界 いもす法では R_j + 1 のインデックスにアクセスするため、配列のサイズは \(N + 2\) 以上確保しておく必要があります。1-based indexing（1始まりのインデックス）で実装すると、直感的かつ安全に配列外参照を防ぐことができます。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    long long T;
    if (!(cin >> N >> M >> T)) return 0;

    vector<long long> F(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> F[i];
    }

    vector<long long> diff(N + 2, 0);
    for (int j = 0; j < M; ++j) {
        int L, R;
        long long D;
        cin >> L >> R >> D;
        diff[L] += D;
        diff[R + 1] -= D;
    }

    int ans = 0;
    long long current_S = 0;
    for (int i = 1; i <= N; ++i) {
        current_S += diff[i];
        if (current_S >= F[i] - T) {
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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