概要

\(N\) 個の花壇に対して、指定された範囲 \([X_j, Y_j]\) に水分量 \(Z_j\) を加える操作を \(M\) 回行い、最終的な水分量が \(K\) 以上である花壇の個数を求める問題です。

考察

まず、素朴な方法（シミュレーション）を考えてみます。 各水やりごとに、花壇 \(X_j\) から \(Y_j\) までループを回して水分量を加算していくと、1回の水やりで最大 \(N\) 回の加算が発生します。水やりは \(M\) 回行われるため、全体の計算量は \(O(NM)\) となります。 制約を見ると \(N, M \leq 2 \times 10^5\) であるため、\(N \times M\) は最大で \(4 \times 10^{10}\) となり、実行時間制限に間に合いません。

効率的に範囲更新を行うために、「いもす法（差分配列）」を利用します。 いもす法を用いると、範囲 \([X, Y]\) への加算操作を、配列の2箇所を更新するだけの \(O(1)\) の操作に変換できます。すべての操作が終わった後に累積和をとることで、各地点の最終的な加算量を \(O(N)\) で求めることができます。

アルゴリズム

いもす法の手順

1. 長さ \(N+2\) の差分配列 diff を用意し、すべて \(0\) で初期化します。
2. 各水やり \((X_j, Y_j, Z_j)\) に対して、以下のように更新します：
   • diff[X_j] に \(Z_j\) を加える
   • diff[Y_j + 1] から \(Z_j\) を引く
3. \(1\) から \(N\) まで順番に diff の累積和を計算します。
   • 地点 \(i\) における累積和 current_increase は、その地点における「水分量の合計増加量」を表します。
4. 各地点 \(i\) について、初期の水分量 \(L_i\) と合計増加量 current_increase の和が \(K\) 以上であるか判定し、カウントします。

具体例

例えば、花壇が3つ（初期値すべて0）あり、範囲 \([1, 2]\) に \(5\) を加える場合： - diff[1] += 5 - diff[3] -= 5 (2の次の要素) - 累積和をとると： - \(i=1\): \(5\) - \(i=2\): \(5 + 0 = 5\) - \(i=3\): \(5 + 0 - 5 = 0\) となり、正しく範囲 \([1, 2]\) にのみ \(5\) が加算されます。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みに \(O(N + M)\)
  • \(M\) 回の範囲更新操作に \(O(M)\)
  • 累積和の計算と判定に \(O(N)\)
  • 全体として \(N, M\) に対して線形時間で動作するため、十分に高速です。
• 空間計算量: \(O(N)\)
  • 初期値を格納する配列 \(L\) と、差分配列 diff のために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonでは input() を繰り返すと遅いため、sys.stdin.read().split() などで一括して読み込む手法が有効です。

• 配列のサイズ: 差分配列で Y_j + 1 のインデックスにアクセスするため、配列のサイズを \(N+2\) 程度確保しておくと、境界条件（\(Y_j = N\) のときなど）を気にせずに実装できます。

• 1-indexed と 0-indexed: 問題文は花壇の番号が \(1\) から始まりますが、Pythonのリストは \(0\) から始まります。初期値のリスト \(L\) と差分配列 diff のインデックスの対応関係に注意が必要です。

  ソースコード

import sys

def solve():
    # 入力を一度に読み込み、空白で分割してトークンのリストを作成します。
    # これはPythonにおいて大量の入力を高速に処理する一般的な手法です。
    data = sys.stdin.read().split()
    if not data:
        return
    
    # イテレータを使用してデータを順番に取得します。
    it = iter(data)
    
    # N: 花壇の数, M: 水やりの回数, K: 水分量の基準値
    N = int(next(it))
    M = int(next(it))
    K = int(next(it))
    
    # 各花壇の初期水分量 L_i を読み込みます。
    L = [int(next(it)) for _ in range(N)]
    
    # いもす法（累積和を用いた範囲更新）のための差分配列を準備します。
    # 花壇の番号は1からNまでなので、サイズは N+2 とします。
    diff = [0] * (N + 2)
    
    # M 回の水やり情報を処理します。
    for _ in range(M):
        # x: 開始花壇, y: 終了花壇, z: 増加する水分量
        x = int(next(it))
        y = int(next(it))
        z = int(next(it))
        
        # 差分配列の更新
        diff[x] += z
        if y + 1 <= N:
            diff[y+1] -= z
            
    # 各花壇の最終的な水分量を計算し、基準値 K 以上であるか判定します。
    ans = 0
    current_increase = 0
    for i in range(1, N + 1):
        # 差分配列の累積和が、その花壇における水分量の合計増加量になります。
        current_increase += diff[i]
        
        # 初期水分量 L[i-1] に増加量を足したものが最終的な水分量です。
        if L[i-1] + current_increase >= K:
            ans += 1
            
    # 結果を出力します。
    print(ans)

if __name__ == '__main__':
    solve()

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