概要

数直線上の \(N\) 個の区間 \([L_i, R_i]\) にペンキを塗り、その中で \(K\) 回以上重ねて塗られた領域の合計長さを求める問題です。

考察

座標の大きさとナイーブな手法の限界

まず、座標の範囲が \(0 \leq L_i, R_i \leq 10^9\) と非常に大きいことに注目します。 もし座標が小さければ、「いもす法」のように配列を用意して各地点の塗り回数をカウントできますが、\(10^9\) サイズの配列を確保することはメモリと時間の両面で不可能です。

重要な気づき

塗り回数が変化するのは、与えられた区間の端点である \(L_i\) または \(R_i\) の地点のみです。 それ以外の地点（例えば \(L_i\) と \(R_i\) の間にある整数でない地点など）では、塗り回数が急に変わることはありません。

したがって、すべての区間の端点を「イベント」として抽出し、数直線を左から右へ走査していく平面走査（スイープライン）の考え方を適用することで、効率的に解くことができます。

アルゴリズム

以下の手順で解を進めます。

1. イベントの抽出: 各区間 \([L_i, R_i]\) について、以下の 2 つの情報をイベントとして記録します。

   • 地点 \(L_i\) で塗り回数が \(+1\) される。
   • 地点 \(R_i\) で塗り回数が \(-1\) される。 合計で \(2N\) 個のイベントが発生します。

2. イベントのソート: 抽出したイベントを座標の昇順に並べ替えます。これにより、数直線を左から順に見ていく準備が整います。

3. 走査と集計: 現在の塗り回数を保持する変数 current_layers を 0 で初期化し、ソートされたイベントを一つずつ処理します。

   • 前回のイベントの座標を prev_x、現在のイベントの座標を x とします。
   • 区間 [prev_x, x] において、塗り回数は一定（current_layers）です。
   • もし current_layers >= K であれば、その区間の長さ x - prev_x を答えに加算します。
   • その後、現在のイベントによる変化分（\(+1\) または \(-1\)）を current_layers に反映させます。

この方法であれば、座標がどれほど大きくても、イベントの数（\(2N\) 個）に依存した計算量で答えを求めることができます。

計算量

• 時間計算量: \(O(N \log N)\)
  • イベントの抽出に \(O(N)\)、イベントのソートに \(O(N \log N)\)、走査に \(O(N)\) かかります。全体のボトルネックはソート部分です。
• 空間計算量: \(O(N)\)
  • \(2N\) 個のイベントをリストに格納するため、 \(O(N)\) のメモリを使用します。

実装のポイント

• 同じ座標に複数のイベントがある場合: Pythonの sort() を用いてイベントをソートすると、座標が同じイベントが連続して並びます。この場合、走査の過程で x - prev_x が \(0\) になるため、同じ座標で塗り回数が一気に変化しても正しく計算されます。

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と比較的大きいため、Pythonでは sys.stdin.read().split() を使って一括で入力を読み込むなどの工夫をすると実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # Read all input at once and split into a list of strings for fast processing
    data = sys.stdin.read().split()
    if not data:
        return
    
    # First two elements are N (number of operations) and K (threshold)
    N = int(data[0])
    K = int(data[1])
    
    # Each paint operation [L_i, R_i] creates two events for the sweep-line:
    # 1. At L_i, the number of paint layers increases by 1.
    # 2. At R_i, the number of paint layers decreases by 1.
    events = [None] * (2 * N)
    for i in range(N):
        l = int(data[2 + 2 * i])
        r = int(data[3 + 2 * i])
        events[2 * i] = (l, 1)
        events[2 * i + 1] = (r, -1)
        
    # Sort all events by their coordinate.
    # Python's sort (Timsort) is O(M log M) where M is the number of events.
    # If multiple events have the same coordinate, the order of their deltas 
    # does not affect the final answer because the distance between them is 0.
    events.sort()
    
    total_length = 0
    current_layers = 0
    # prev_x stores the coordinate of the last processed event.
    # This is used to calculate the length of the interval between consecutive events.
    prev_x = events[0][0]
    
    for x, delta in events:
        # If the region between the previous event and the current event
        # was covered by at least K layers of paint, add its length to the total.
        if current_layers >= K:
            total_length += x - prev_x
        
        # Update the number of overlapping paint layers for the next interval.
        current_layers += delta
        # Update the boundary coordinate to the current one.
        prev_x = x
        
    # Output the calculated total length.
    sys.stdout.write(str(total_length) + '\n')

if __name__ == '__main__':
    solve()

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