概要

N本の植物があり、それぞれに初期の水分量が設定されている。M回の水やり操作で、指定区間の植物の水分量を増やした後、最終的に水分量がK以上の植物の本数を求める問題。

考察

この問題の素朴な解法として、「各水やりについて、区間 \([L_j, R_j]\) のすべての植物の水分量を直接1ずつ増やす」という方法が考えられます。しかし、この方法では最悪計算量が \(O(M \times N)\) となり、制約 \(M, N \leq 2 \times 10^5\) では間に合いません（最大で \(4 \times 10^{10}\) 回の操作が必要になりTLE）。

そこで、区間に対する一様な加算を効率的に行う方法として「差分配列（imos法）」を利用します。差分配列を使えば、区間への加算を \(O(1)\) で処理でき、最後に累積和を取ることで各要素への加算回数が求められます。

例えば、区間 \([2, 5]\) に+1する場合、差分配列のインデックス1に+1、インデックス5に-1を加えることで、区間に対する更新を高速に表現できます。

このテクニックにより、全体の水やりによる増加分を高速に求めることができ、その後各植物の最終的な水分量を計算してK以上かどうか判定すれば答えが出ます。

アルゴリズム

1. 各植物の初期水分量 \(A_i\) を読み込む。
2. 差分配列 diff をサイズ \(N+1\) で準備する（境界処理のため1つ多く）。
3. 各水やり \(j\) に対して：
   • 区間 \([L_j, R_j]\) に+1を加算 → diff[L_j - 1] += 1, diff[R_j] -= 1
4. 差分配列の累積和を計算し、各植物への水やり回数を得る。
5. 各植物について「初期水分量 + 水やり回数」が \(K\) 以上ならカウントアップ。
6. カウント結果を出力。

計算量

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

実装のポイント

• 差分配列のインデックスは0始まりなので、区間 \([L, R]\) は diff[L - 1] と diff[R] に更新することに注意。
• 最後の累積和は diff[:N] に対して行い、diff[N] はダミー要素として使うだけ。
• 入力を高速に読み込むため、sys.stdin.read() を使用している。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    A = [int(data[i]) for i in range(idx, idx + N)]; idx += N
    
    # 差分配列を用意
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L = int(data[idx]); idx += 1
        R = int(data[idx]); idx += 1
        diff[L-1] += 1
        diff[R] -= 1
    
    # 累積和で水やり回数を計算
    water_added = list(accumulate(diff[:-1]))
    
    # 最終的な水分量を計算し、K以上になる植物をカウント
    count = 0
    for i in range(N):
        final_moisture = A[i] + water_added[i]
        if final_moisture >= K:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。