概要

数直線上に \(N\) 個の区間でペンキを重ね塗りしたとき、\(K\) 回以上塗られた部分の合計の長さを求める問題です。いもす法（イベントソート） を用いて効率的に解きます。

考察

素朴なアプローチの問題点

座標の範囲が最大 \(10^9\) と非常に大きいため、各整数座標ごとに塗られた回数を配列で管理する方法では、メモリも時間も足りません。

重要な気づき

ペンキの塗られた回数が変化するのは、各区間の左端 \(L_i\) と右端 \(R_i\) の座標だけです。つまり、変化が起きるイベント点は高々 \(2N\) 個しかありません。

例えば、\(N=3, K=2\) で区間 \([1, 5], [3, 7], [4, 6]\) にペンキを塗る場合を考えます。

座標:  1   3   4   5   6   7
       +1      +1
           +1
                   -1
                       -1
                           -1
累積:  1   2   3   2   1   0

座標 \(1\) で塗り回数が \(1\) に、座標 \(3\) で \(2\) に、座標 \(4\) で \(3\) に……と変化します。隣り合うイベント点の間では塗り回数は一定なので、回数が \(K\) 以上のまま続く区間の長さを足し合わせればよいのです。

アルゴリズム

いもす法（座標圧縮 + イベントソート） を使います。

1. イベントの生成: 各区間 \([L_i, R_i]\) に対して、座標 \(L_i\) に \(+1\)、座標 \(R_i\) に \(-1\) というイベントを記録します。
2. ソート: イベントを座標の昇順にソートします。
3. 走査: 左から順にイベントを処理し、現在の塗り回数 count を管理します。
   • あるイベント点 pos を処理するとき、直前のイベント点 prev から pos までの区間において、count >= K ならその区間の長さ pos - prev を答えに加算します。
   • その後、count にイベントの差分 delta を加えます。

具体例での動作（\(N=3, K=2\), 区間 \([1,5],[3,7],[4,6]\)）

pos	delta	加算前の count	加算する長さ	加算後の count
1	+1	0 (< 2, 加算なし)	0	1
3	+1	1 (< 2, 加算なし)	0	2
4	+1	2 (≥ 2) → \(4-3=1\)	1	3
5	-1	3 (≥ 2) → \(5-4=1\)	1	2
6	-1	2 (≥ 2) → \(6-5=1\)	1	1
7	-1	1 (< 2, 加算なし)	0	0

合計: \(1 + 1 + 1 = 3\)

計算量

• 時間計算量: \(O(N \log N)\)（イベントのソートがボトルネック）
• 空間計算量: \(O(N)\)（イベントの保存に最大 \(2N\) 個）

実装のポイント

• defaultdict(int) を使うことで、同じ座標に複数のイベントがある場合（例えば複数の区間が同じ左端を持つ場合）も自然にまとめられます。

• 走査の際、先に前の区間の長さを加算してから count を更新する順序が重要です。count はイベント点 prev から pos の間の塗り回数を表しているため、pos でのイベント処理前に長さを計算する必要があります。

• 座標が最大 \(10^9\) ですが、イベント点のみを扱うため座標圧縮を明示的に行わずとも問題ありません。

  ソースコード

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    events = defaultdict(int)
    
    for i in range(N):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        events[L] += 1
        events[R] -= 1
    
    sorted_events = sorted(events.items())
    
    total = 0
    count = 0
    prev = None
    
    for pos, delta in sorted_events:
        if prev is not None and count >= K:
            total += pos - prev
        count += delta
        prev = pos
    
    print(total)

main()

---

この解説は claude4.6opus-thinking によって生成されました。