概要

観測地点ごとに降雪範囲に含まれた回数を数え、その回数がK以上である地点の数を求める問題です。

考察

各地点の積雪回数を直接計算しようとすると、最大\(N = 10^6\)地点、\(M = 2 \times 10^5\)回の降雪に対して、各降雪で最大\(N\)地点を更新する必要があり、最悪\(O(N \times M)\)の計算量となり、制限時間内に計算できません。

効率的に解くためには、イベントソートと累積和の考え方を組み合わせます。各降雪を「開始イベント」と「終了イベント」に分解し、地点順にソートすることで、各地点を通過する際の積雪回数の変化を追跡できます。

アルゴリズム

1. イベントの作成: 各降雪範囲\([L_i, R_i]\)について、

   • 地点\(L_i\)で+1（降雪開始）
   • 地点\(R_i+1\)で-1（降雪終了） という2つのイベントを作成します。

2. イベントのソート: すべてのイベントを地点の昇順、同じ地点では-1（終了）を先に処理するようにソートします。

3. スイープライン: 地点1から順に、現在の積雪回数（current）を管理します。各イベント地点で：

   • 前の地点（prev）から現在の地点（pos）までの区間において、積雪回数がK以上であれば、その区間長（pos - prev）を結果に加算
   • イベントの値（delta）をcurrentに加算して積雪回数を更新
   • 前の地点を現在の地点に更新

4. 結果の出力: 最終的に計算されたK以上の地点の総数を出力します。

計算量

• 時間計算量: \(O(M \log M)\)
  • イベント数は\(2M\)個で、ソートに\(O(M \log M)\)かかります
  • スイープライン処理は\(O(M)\)です
• 空間計算量: \(O(M)\)
  • イベントを格納するためのメモリです

実装のポイント

• イベントは（地点, 変化量）のタプルで表現します

• ソート時、同じ地点では終了イベント（-1）を先に処理する必要があります（降雪範囲が右端を含むため）

• 最後の地点からN+1までの処理は必要ありません（地点は1からNまでしかないため）

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
    
    n = int(data[0])
    m = int(data[1])
    k = int(data[2])
    
    events = []
    index = 3
    for i in range(m):
        L = int(data[index])
        R = int(data[index+1])
        index += 2
        events.append((L, 1))
        events.append((R + 1, -1))
    
    events.sort(key=lambda x: (x[0], x[1]))
    
    current = 0
    result = 0
    prev = 1
    for event in events:
        pos, delta = event
        if pos > prev:
            if current >= k:
                result += (pos - prev)
        current += delta
        prev = pos
    
    print(result)

if __name__ == "__main__":
    main()

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