概要

区間 \([L_j, R_j]\) に対して一律に \(+1\) を \(M\) 回行った結果、各植物の最終水分量が \(K\) 以上になる本数を数えます。
区間加算を高速に処理するために「差分配列（いもす法）」を使います。

考察

重要な気づき

各水やりは「連続区間の全要素に \(+1\)」という操作です。
このような区間更新をそのまま毎回配列に反映すると、1 回の水やりで最大 \(O(N)\) 要素を書き換えることになり、全体で \(O(NM)\) になります。

• 制約は \(N, M \le 2 \times 10^5\)
• もし素朴にやると最悪で \(N \times M = 4 \times 10^{10}\) 回程度の更新になり、時間内に終わりません（TLE）。

どう解決するか（差分配列）

区間 \([L, R]\) に \(+1\) を加える操作は、差分配列 diff を使うと次の 2 点の更新で表現できます。

• diff[L] += 1
• diff[R+1] -= 1（ただし \(R+1\) が範囲内なら）

最後に diff の累積和を取ると、各位置 \(i\) に「何回水やりされたか（加算回数）」が復元できます。

具体例

\(N=5\)、区間 \([2,4]\)（1-indexed）に \(+1\) の場合（0-indexed に直すと \([1,3]\)）： - diff[1] += 1 - diff[4] -= 1

diff を左から累積すると、位置 1〜3 だけが +1 され、それ以外は 0 のままになります。

アルゴリズム

1. 入力で初期水分量配列 \(A\) を受け取る。
2. 長さ \(N+1\) の差分配列 diff を 0 で初期化する。
3. 各水やり \((L, R)\) について（0-indexed に直す）
   
   • diff[L] += 1
     
   • もし \(R+1 < N\) なら diff[R+1] -= 1
4. diff の累積和 cur を取りながら、各 \(i\) について
   • 最終水分量は \(A_i + cur\)
   • これが \(K\) 以上なら答えを 1 増やす
5. 答えを出力する。

計算量

• 時間計算量: \(O(N + M)\)
  （各水やりは \(O(1)\)、最後の累積和と判定が \(O(N)\)）
• 空間計算量: \(O(N)\)
  （差分配列 diff と配列 \(A\)）

実装のポイント

• 入力の \(L_j, R_j\) は 1-indexed なので、コードでは -1 して 0-indexed に直す。

• diff[R+1] にアクセスするときは、\(R+1\) が配列範囲内（\(<N\)）かチェックする（コードでは if R + 1 < N:）。

• 差分配列は「累積和を取って初めて意味を持つ」ので、最後に cur += diff[i] を忘れない。

• \(N, M\) が大きいので、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)

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

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

    ans = 0
    cur = 0
    for i in range(N):
        cur += diff[i]
        if A[i] + cur >= K:
            ans += 1

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

---

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