概要

この問題は、N個の区間が与えられたとき、K回以上塗られた部分の合計の長さを求める問題です。

考察

素朴なアプローチとして、各座標での塗り回数を直接数え上げる方法が考えられますが、座標の範囲が最大10^9まで広いため、全座標を調べることはできません。また、Nが最大200,000であることから、効率的なアルゴリズムが必要です。

重要な観察は、塗り回数の変化が整数座標でのみ起こることです。つまり、区間と区間の間では塗り回数は一定であり、変化するのは区間の端点のみです。この性質を利用して、イベントベースのアプローチが有効です。

アルゴリズム

イベント駆動のスイープラインアルゴリズムを使用します。具体的な手順は以下の通りです：

1. イベントの生成: 各区間の開始点（L_i）では+1、終了点（R_i）では-1のイベントを作成します
2. イベントのソート: すべてのイベントを座標の昇順にソートします
3. スイープライン処理: 左から右へスイープしながら処理します：
   • 現在の塗り回数（current_count）を管理
   • K回以上塗られている区間の開始点（start_segment）を追跡
   • イベント点間の区間長を加算（条件を満たす場合のみ）

具体的には、各イベント点間の区間において： - 塗り回数がK以上なら、その区間長を合計に加算 - 塗り回数の変化に応じて、K回以上塗られる区間の開始・終了を判定

計算量

• 時間計算量: \(O(N \log N)\)（イベントのソートが支配的）
• 空間計算量: \(O(N)\)（イベントの格納に必要なメモリ）

実装のポイント

• イベントを（座標, 変化量）のタプルで表現
• 同じ座標に複数のイベントがある場合、ソート順序に注意（特に+1と-1が同じ座標にある場合）
• 現在の塗り回数と前回の座標を保持しながら処理
• K回以上塗られる区間の開始点を適切に管理するフラグ変数を使用

このアルゴリズムは、座標の範囲が広くても効率的に処理でき、整数演算のみを使用するため正確な結果が得られます。

ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    K = int(data[1])
    events = []
    index = 2
    for i in range(n):
        L = int(data[index])
        R = int(data[index+1])
        index += 2
        events.append((L, 1))
        events.append((R, -1))
    
    events.sort()
    
    total_length = 0
    current_count = 0
    prev_x = 0
    start_segment = None
    
    for x, event_type in events:
        if current_count >= K and start_segment is not None:
            total_length += x - prev_x
        
        current_count += event_type
        
        if current_count >= K and start_segment is None:
            start_segment = x
        elif current_count < K and start_segment is not None:
            start_segment = None
        
        prev_x = x
    
    print(total_length)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。