概要

\(N\) 本の植物に対して、「範囲 \([L, R]\) にあるすべての植物の水分量を \(1\) 増やす」という操作を \(M\) 回行います。最終的な各植物の水分量が閾値 \(K\) 以上であるものの個数を求める問題です。

考察

素朴なアプローチ

各水やり操作に対して、毎回 \(L\) から \(R\) までの植物をループで回して水分量を増やしていくとどうなるでしょうか。 最悪の場合、1回の操作で \(N\) 本すべての植物に水を与えることになり、それが \(M\) 回繰り返されるため、計算量は \(O(N \times M)\) となります。 本問題の制約は \(N, M \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません（TLE）。

効率的なアプローチ（いもす法）

「特定の範囲に一律で値を加算する」という操作を高速化するために、「いもす法（差分配列）」という手法を使います。 いもす法では、範囲 \([L, R]\) に \(1\) を加える操作を、以下の2つの点への更新だけで表現します。 1. 始点 \(L\) に \(+1\) する（ここから増加が始まる） 2. 終点の次 \(R+1\) に \(-1\) する（ここで増加が終わる）

すべての操作が終わった後に、配列の端から累積和をとることで、各地点で合計いくら加算されたかを \(O(N)\) で求めることができます。これにより、全体で \(O(N + M)\) の計算量で解くことが可能になります。

アルゴリズム

1. 差分配列の用意: 長さ \(N+2\) の配列 diff を \(0\) で初期化して用意します（1-indexedでの管理や \(R+1\) へのアクセスを考慮するため）。
2. 水やりの記録: \(M\) 回の水やり操作 \((L_j, R_j)\) に対して、以下を行います。
   • diff[L_j] += 1
   • diff[R_j + 1] -= 1
3. 累積和と判定:
   • 変数 current_water（現在の累積加算量）を \(0\) で初期化します。
   • 植物 \(i = 1\) から \(N\) まで順に以下を繰り返します。
     • current_water += diff[i] と更新する。
     • 植物 \(i\) の最終的な水分量は A[i] + current_water となる。
     • これが \(K\) 以上であれば、答えのカウントを \(1\) 増やす。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みに \(O(N + M)\)、水やり操作の記録に \(O(M)\)、累積和の計算と判定に \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 植物の初期値を保持する配列と、差分配列を管理するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) や \(M\) が大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() などを使って一括で読み込む方が実行時間を短縮できます。

• インデックスの管理: 問題文は 1-indexed（植物の番号が 1 から始まる）ですが、プログラム内での配列の扱いや \(R+1\) の境界条件に注意して配列サイズを確保する必要があります。今回のコードでは N + 2 のサイズを確保することで、範囲外参照を防いでいます。

  ソースコード

import sys

def solve():
    # Fast input reading: read the entire input and split by whitespace
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: number of plants, M: number of watering operations, K: threshold
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    
    # A: initial moisture levels for plants 1 to N
    # Using list(map(int, ...)) on a slice is efficient in Python
    A = list(map(int, input_data[3 : 3 + N]))
    
    # diff: difference array for the imos method (range updates)
    # diff[i] stores the change in moisture level starting at plant i.
    # Size N + 2 is used to handle 1-based indexing and the boundary at R + 1.
    diff = [0] * (N + 2)
    
    # Process M watering operations
    # Each operation is given as a range [L, R]
    idx = 3 + N
    for _ in range(M):
        L = int(input_data[idx])
        R = int(input_data[idx + 1])
        # Increment water level at index L, decrement after index R
        diff[L] += 1
        diff[R + 1] -= 1
        idx += 2
        
    # ans_count: number of plants whose final moisture level is at least K
    ans_count = 0
    # current_water: cumulative water added to the plant currently being evaluated
    current_water = 0
    
    # Evaluate each plant from 1 to N
    for i in range(N):
        # Update the cumulative water using the difference array
        # A[i] corresponds to plant i+1, so we look at diff[i+1]
        current_water += diff[i + 1]
        # Final moisture = initial moisture + total water added
        if A[i] + current_water >= K:
            ans_count += 1
            
    # Output the final result to standard output
    sys.stdout.write(str(ans_count) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。