概要

数直線上の区間に複数回ペンキを塗った結果、\(K\) 回以上重なった部分の合計の長さを求める問題です。

考察

この問題では、各ペイント区間 \([L_i, R_i]\) に対して、その区間内のすべての点の塗られた回数が 1 増えるため、単純に各区間をシミュレーションすると、非常に大きな領域（最大 \(10^9\)）を扱うことになり、時間的にもメモリ的にも無理があります。

重要な観察として、「塗られた回数が変わる場所」は各区間の端点（\(L_i\) または \(R_i\)）だけであるということです。つまり、塗り状況が変わる可能性があるのは高々 \(2N\) 点だけであり、これらを効率的に処理することで問題を解くことができます。

そこで、イベントベースの処理を行います。具体的には、各区間の開始点に「+1」イベント、終了点に「-1」イベントを設定し、これらのイベントを座標順に処理していきます。イベントを処理しながら現在の塗られた回数（current_count）を管理し、それが \(K\) 以上であった区間の長さを累積していけば答えが得られます。

ここで注意すべきは、同じ座標に「+1」と「-1」の両方のイベントがある場合、+1 を先に処理しないと、本来塗るべき区間が欠落してしまうことです。例えば、区間 \([2, 5)\) と \([5, 8)\) があったとき、5 でカウントが一旦 0 に戻ると見なされてしまうと、連続性が失われます。そのため、同じ座標では +1 を -1 よりも先に処理する必要があります。

アルゴリズム

1. 各区間 \([L_i, R_i]\) に対して、以下のようなイベントを作成します：
   • 開始点 \(L_i\) に +1 のイベント
   • 終了点 \(R_i\) に -1 のイベント
2. すべてのイベントを座標の昇順にソートします。同じ座標の場合は +1 を -1 よりも先に処理するようにします。
3. ソートされたイベントを順番に処理しながら、以下のようにシミュレートします：
   • 現在位置までの間に、current_count >= K だった区間があれば、その長さを答えに加算します。
   • 現在のイベントに応じて current_count を更新します。
4. 最終的な合計長を出力します。

具体例

入力が以下の場合を考えます：

N = 2, K = 2
L1 = 1, R1 = 5
L2 = 3, R2 = 7

イベントリストは：

• (1, +1)
• (3, +1)
• (5, -1)
• (7, -1)

処理の流れ：

pos	delta	current_count	区間判定	加算長
1	+1	1	0→1	0
3	+1	2	1→2 → OK	3-1=2
5	-1	1	2→1 → NG	5-3=2
7	-1	0	1→0	0

合計：4

計算量

• 時間計算量: \(O(N \log N)\) （ソートが支配）
• 空間計算量: \(O(N)\) （イベントリスト）

実装のポイント

• イベントのソート時に (pos, -delta) のようにして、+1 を先に行うように工夫する。

• 現在のカウントが K 以上だったかどうかを判定するタイミングが重要。

• 座標が整数なので、区間は半開区間 \([L_i, R_i)\) と見なすことも可能だが、この問題では閉区間 \([L_i, R_i]\) であることに注意。

  ソースコード

import sys
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    
    events = []
    index = 2
    for _ in range(N):
        L = int(data[index])
        R = int(data[index+1])
        events.append((L, +1))
        events.append((R, -1))
        index += 2
    
    # 座標をソートする（同じ座標なら+1を-1より先に処理）
    events.sort(key=lambda x: (x[0], -x[1]))
    
    current_count = 0
    total_length = 0
    prev_pos = 0
    
    for pos, delta in events:
        # カウントがK以上だった区間の長さを加算
        if current_count >= K:
            total_length += pos - prev_pos
        
        current_count += delta
        prev_pos = pos
    
    print(total_length)

if __name__ == "__main__":
    main()

---

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