概要

区間加算（連続した花壇への水やり）を \(M\) 回行ったあと、各花壇の最終水分量が \(K\) 以上になる個数を数える問題です。

考察

各水やりは「区間 \([X_j, Y_j]\) に \(Z_j\) を足す」という操作です。素朴に考えると、毎回その区間のすべての花壇に加算していけばよいですが、これをそのまま実装すると最悪で

• 1 回の水やりが区間長 \(O(N)\)
  
• 水やりが \(M\) 回

となり、合計 \(O(NM)\) です。制約では \(N, M \le 2 \times 10^5\) なので、最悪 \(4 \times 10^{10}\) 回程度の更新が発生し、確実に時間切れになります。

ここで重要な気づきは、「区間全体に同じ値を足す操作」は、差分（増分の変化点）だけを記録しておき、最後に累積和でまとめて復元できるということです。

例えば \(N=5\) のとき、区間 \([2,4]\) に \(+3\)（1-indexed）をしたいなら、 - 2 番目から「+3 が効き始める」 - 5 番目（=4+1）から「+3 が効かなくなる」

という情報だけあれば、左から累積して各位置の加算量を作れます。

アルゴリズム

差分配列（いわゆるいもす法）を使います。

1. 長さ \(N\) の初期水分量配列 \(L\) を読む。
2. 差分配列 diff（長さ \(N+1\) でもよいが、実装では \(N+1\) を確保しつつ参照は \(0..N-1\)）を 0 で初期化する。
3. 各クエリ（\(X, Y, Z\)）について（0-index に直す）
   
   • diff[X] += Z（ここから増える）
   • もし Y+1 < N なら diff[Y+1] -= Z（ここで増加が終わる）
4. 左から add を累積和として計算する：
   
   • add += diff[i]
     
   • 最終水分量は L[i] + add
     
   • これが \(K\) 以上ならカウントする
5. カウントを出力する。

これにより、各区間操作を「両端の 2 点の更新」に変換でき、最後の 1 回の走査で全花壇の増加量が復元できます。

計算量

• 時間計算量: \(O(N + M)\)（差分更新が \(M\) 回、累積和と判定が \(N\) 回）
• 空間計算量: \(O(N)\)（配列 \(L\) と diff）

実装のポイント

• 入力は 1-indexed なので、コードでは x = X-1, y = Y-1 に直して扱います。

• diff[y+1] -= z は、y+1 が配列範囲内のときだけ行います（y が最後の要素なら「減らす地点」が存在しないため）。

• \(N, M\) が大きいので、Python では sys.stdin.buffer.read() の一括読み込みのような高速入力が有効です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    K = next(it)

    L = [next(it) for _ in range(N)]
    diff = [0] * (N + 1)

    for _ in range(M):
        x = next(it) - 1
        y = next(it) - 1
        z = next(it)
        diff[x] += z
        if y + 1 < N:
            diff[y + 1] -= z

    cnt = 0
    add = 0
    for i in range(N):
        add += diff[i]
        if L[i] + add >= K:
            cnt += 1

    sys.stdout.write(str(cnt))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。