概要

\(N\)個の照明に対して\(M\)回の区間スイッチ操作を行った後、点灯している照明の個数を求める問題です。

考察

各照明は複数回の操作によって点灯/消灯が切り替わります。素朴なアプローチでは、各照明に対して\(M\)回の操作の影響を調べると\(O(NM)\)の時間がかかり、制約条件(\(N \leq 10^6\), \(M \leq 2 \times 10^5\))では実行時間がかかりすぎます。

代わりに、区間操作を効率的に処理する方法が必要です。各照明が点灯するかどうかは、その照明に対して行われた操作の回数の偶奇によって決まります（偶数回なら消灯、奇数回なら点灯）。そこで、各位置での操作回数の変化をイベントとして管理し、スイープライン法を用いて効率的に計算します。

アルゴリズム

1. イベントの作成: 各操作\([L_j, R_j]\)について、\(L_j\)で操作回数が+1、\(R_j+1\)で操作回数が-1するイベントを作成します。
2. イベントのソート: イベントを位置順にソートします。
3. スイープライン: 左から右へスイープしながら、現在の操作回数(current)を追跡します。各イベント間の区間では操作回数が一定なので、その区間長と操作回数の偶奇から点灯している照明の数を計算します。
4. 結果の計算: 最後のイベントから末尾までの区間も同様に処理し、点灯している照明の総数を求めます。

計算量

• 時間計算量: \(O(M \log M)\)
  • イベントのソートが支配的で、\(2M\)個のイベントをソートします
• 空間計算量: \(O(M)\)
  • イベントを格納するためのメモリを使用します

実装のポイント

• イベントは(位置, 変化量)のタプルで管理します

• 区間の端点処理に注意します（\(R_j+1\)を終了点とすること）

• 最後のイベント以降の区間も忘れずに処理します

• 現在の操作回数の偶奇をチェックして点灯数を計算します

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    events = []
    for i in range(M):
        L = int(data[idx])
        R = int(data[idx + 1])
        idx += 2
        events.append((L, 1))
        events.append((R + 1, -1))
    
    events.sort()
    count = 0
    current = 0
    prev = 1
    total_on = 0
    
    for event in events:
        pos, typ = event
        if pos > prev:
            segment_length = pos - prev
            if current % 2 == 1:
                total_on += segment_length
        current += typ
        prev = pos
        
    if prev <= N:
        segment_length = N - prev + 1
        if current % 2 == 1:
            total_on += segment_length
            
    print(total_on)

if __name__ == "__main__":
    main()

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