概要

植物の水分量が初期状態で与えられ、複数回の水やりによって特定範囲の植物の水分量が増加するので、最終的に水分量がK以上になった植物の本数を求める問題です。

考察

素朴なアプローチでは、各水やりごとに指定された範囲の植物すべてに対して直接+1する操作を行うと、最悪の場合で各水やりがほぼ全区間をカバーするため、計算量が\(O(N \times M)\)となり、\(N, M\)が最大200,000なので\(4 \times 10^{10}\)回もの操作が必要になり、時間制限に間に合いません。

この問題を効率的に解くためには、区間更新を高速に行える手法が必要です。ここでは「いもす法」と呼ばれるアルゴリズムを用いることで、区間更新を定数時間で記録し、最後にまとめて計算することができます。

アルゴリズム

1. 差分配列の作成: 長さ\(N+1\)の配列diffを作成します（0-indexed）
2. クエリ処理: 各水やりクエリ\((L_j, R_j)\)に対して:
   • diff[L] += 1（区間の開始位置）
   • diff[R+1] -= 1（区間の終了位置の次の位置）
3. 累積和の計算: 差分配列の累積和を計算することで、各植物が受けた水やりの回数を求めます
4. 判定: 各植物\(i\)について、初期値\(A_i\)に水やりの回数を加算し、\(K\)以上かどうかを判定してカウントします

この方法では、\(M\)回のクエリ処理が\(O(1)\)、累積和の計算が\(O(N)\)で完了するため、全体で\(O(N + M)\)の効率的な計算が可能です。

計算量

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

実装のポイント

• 配列のインデックスに注意: 問題は1-indexedですが、コードでは0-indexedで処理します

• 差分配列のサイズは\(N+1\)にすることで、\(R+1\)が配列の範囲外になるのを防ぎます

• 累積和を計算する際は、現在の値を保持する変数currentを使い、各位置で差分を加算しながら処理します

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    it = iter(data)
    N = int(next(it)); M = int(next(it)); K = int(next(it))
    A = [int(next(it)) for _ in range(N)]
    queries = []
    for _ in range(M):
        L = int(next(it)) - 1
        R = int(next(it)) - 1
        queries.append((L, R))
    
    diff = [0] * (N + 1)
    for L, R in queries:
        diff[L] += 1
        diff[R + 1] -= 1
    
    count = 0
    current = 0
    for i in range(N):
        current += diff[i]
        if A[i] + current >= K:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。