概要

\(N\) 個の花壇に対して \(M\) 回の区間加算クエリを処理し、最終的に水分量が \(K\) 以上の花壇の個数を数える問題です。いもす法（差分配列）を使って効率的に解きます。

考察

素朴なアプローチの問題点

愚直に各水やり操作で区間内のすべての花壇の水分量を更新すると、1回の水やりで最大 \(O(N)\) の更新が必要です。これを \(M\) 回繰り返すと、全体で \(O(NM)\) の計算量となり、\(N, M\) が最大 \(2 \times 10^5\) の場合、約 \(4 \times 10^{10}\) 回の操作となりTLE（時間超過）になります。

重要な気づき

この問題は「区間に一様に値を加算する」操作を複数回行うパターンです。このような問題には いもす法（差分配列） が有効です。

いもす法の基本的なアイデアは以下の通りです： - 区間 \([l, r]\) に値 \(z\) を加算する代わりに、差分配列 \(diff\) に対して - \(diff[l]\) に \(+z\)（ここから加算開始） - \(diff[r+1]\) に \(-z\)（ここで加算終了） - 最後に差分配列の累積和を取ると、各位置への加算量が求まる

具体例

\(N = 5\) の花壇に対して、区間 \([2, 4]\) に水分量 \(3\) を加算する場合：

差分配列の初期状態: [0, 0, 0, 0, 0, 0]  (サイズ N+1)
操作後:            [0, +3, 0, 0, -3, 0]
                      ↑位置2      ↑位置5（=4+1）

累積和を計算:      [0, 3, 3, 3, 0, 0]
→ 花壇2,3,4に3が加算されたことがわかる

アルゴリズム

1. サイズ \(N+1\) の差分配列 \(diff\) を \(0\) で初期化する
2. 各水やり操作 \((X_j, Y_j, Z_j)\) に対して：
   • \(diff[X_j - 1]\) に \(Z_j\) を加算（0-indexedに変換）
   • \(diff[Y_j]\) から \(Z_j\) を減算
3. 差分配列の累積和を計算しながら、各花壇 \(i\) について：
   • 初期水分量 \(L_i\) + 加算された水分量 \(\geq K\) ならカウント
4. カウントを出力

計算量

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

  • 差分配列への記録: 各操作 \(O(1)\) × \(M\) 回 = \(O(M)\)
  • 累積和の計算とカウント: \(O(N)\)

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

  • 差分配列のサイズ: \(N + 1\)

実装のポイント

1. インデックスの変換: 問題文では花壇番号が1-indexedですが、配列は0-indexedなので変換が必要です。\(X_j\) は \(X_j - 1\) に、\(Y_j\) はそのまま（終了位置の次なので）\(Y_j\) になります。

2. 差分配列のサイズ: 区間の終端で減算する際に配列外アクセスを防ぐため、サイズを \(N + 1\) にしておきます。

3. オーバーフロー対策: Pythonでは整数のオーバーフローを気にする必要はありませんが、C++などでは水分量の合計が大きくなる可能性があるため、long long 型を使う必要があります。

   ソースコード

def main():
    import sys
    input = sys.stdin.readline
    
    N, M, K = map(int, input().split())
    L = list(map(int, input().split()))
    
    # 差分配列（いもす法）を使用
    # diff[i] は位置 i での増分の変化量
    diff = [0] * (N + 1)
    
    for _ in range(M):
        X, Y, Z = map(int, input().split())
        # 1-indexed から 0-indexed に変換
        diff[X - 1] += Z
        diff[Y] -= Z
    
    # 累積和を計算して各花壇への総水やり量を求める
    water_added = 0
    count = 0
    
    for i in range(N):
        water_added += diff[i]
        if L[i] + water_added >= K:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

この解説は claude4.5opus によって生成されました。