概要

区間に対する「+1 の塗り」を \(N\) 回行った後、塗られた回数が \(K\) 以上になっている部分の長さの合計を求めます。境界は整数にしか現れないので、変化点だけを見れば十分です。

考察

重要な気づき

• ペンキの回数が変化するのは、各作業の端点 \(L_i, R_i\) の位置だけです。
• 端点の間（例えば \(x \in [a, b)\)）では、塗られた回数は一定になります。
  よって「どの区間で回数が \(K\) 以上か」を調べ、その長さを足せば答えになります。

素朴な方法がダメな理由

座標は最大で \(10^9\) まであり、整数点や小区間を全部なめるような方法（配列で管理、1 ずつ進める等）は不可能です（時間もメモリも足りません）。

どう解決するか

「差分（イベント）」を使って、端点での増減だけを記録し、座標順に走査します（いわゆる sweep line / いもす法の連続版）。

例えば区間 \([L, R]\) を 1 回塗るのは、 - \(x = L\) で回数が \(+1\) 増える - \(x = R\) で回数が \(-1\) 減る
と考えられます。これを全区間分集めてソートし、左から累積すれば各区間の塗り回数が分かります。

アルゴリズム

1. 各区間 \([L_i, R_i]\) についてイベントを追加する：
   • \((L_i, +1)\)
   • \((R_i, -1)\)
2. イベントを座標 \(x\) でソートする。
3. 同じ座標に複数イベントがある場合はまとめて（\(d\) を合算して）扱う。
4. 座標列を \(x_0 < x_1 < \dots < x_m\) とする。左から順に
   • 現在の塗り回数 cur に、その点の差分を加える（cur += ds[i]）
   • 区間 \([x_i, x_{i+1})\) の塗り回数は cur で一定なので、
     • cur >= K なら長さ \(x_{i+1} - x_i\) を答えに加算する
5. 合計を出力する。

※本コードでは \([x_i, x_{i+1})\) の形で数えていますが、端点は整数で、境界でしか変化しないため長さの合計は問題文の \([L_i, R_i]\) と矛盾しません（長さは端点の含む/含まないに依らない）。

計算量

• 時間計算量: \(O(N \log N)\)（イベント \(2N\) 個のソートが支配的）
• 空間計算量: \(O(N)\)（イベント保存用）

実装のポイント

• 同じ座標のイベントをまとめる：例えば同じ \(x\) に \(+1\) と \(-1\) が複数あるので、まとめないと処理が煩雑になります（本コードは xs, ds に圧縮）。

• 走査は「隣り合う座標間」だけ：答えに加えるのは常に xs[i+1] - xs[i] の形になります。

• cur += ds[i] をしてから区間を見ることに注意：\(x_i\) から右側の区間の塗り回数を表すためです。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    events = []
    for _ in range(N):
        L, R = map(int, input().split())
        events.append((L, 1))
        events.append((R, -1))

    events.sort()
    xs = []
    ds = []
    for x, d in events:
        if xs and xs[-1] == x:
            ds[-1] += d
        else:
            xs.append(x)
            ds.append(d)

    cur = 0
    ans = 0
    for i in range(len(xs) - 1):
        cur += ds[i]
        if cur >= K:
            ans += xs[i + 1] - xs[i]

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。