概要

各区間に含まれる照明のスイッチを切り替える操作を \(M\) 回行った後、最終的に点灯している照明の数を求める問題。

考察

この問題では、各区間 \([L_j, R_j]\) に対して、それに属する照明の状態（点灯／消灯）を反転させます。素朴な方法として、各操作ごとに該当する照明を一つずつ更新していくと、最悪の場合 \(O(N \times M)\) の計算が必要になります。これは制約条件 \(N \leq 10^6\), \(M \leq 2 \times 10^5\) のもとでは時間内に処理できません（最大で \(2 \times 10^{11}\) 回の計算が必要になる）。

そこで重要な着眼点は「各照明が何回スイッチを押されたか」だけに注目することです。スイッチを偶数回押されると元の状態（消灯）に戻り、奇数回だと点灯します。そのため、「各区間に対する加算処理を高速に行い、最後に各照明が何回操作されたかを求める」ことが求められます。

これは差分配列（いもす法）を用いることで効率的に処理できます。区間 \([L, R]\) へのインクリメントを、差分の形で記録することで、最後に累積和を取ることで各要素の値が得られます。

例えば、照明が4つあるとき、区間 \([2, 3]\) に操作を行うと、差分配列に対して以下のように記録します： - diff[2] += 1 - diff[4] -= 1

その後、diff の累積和を計算することで、各照明の操作回数が得られます。

アルゴリズム

1. 長さ \(N+2\) の差分配列 diff を準備する（境界処理のため余分に取る）。
2. 各操作 \([L_j, R_j]\) について：
   • diff[L_j] += 1
   • diff[R_j + 1] -= 1
3. 差分配列の累積和を計算し、各照明の操作回数を求める。
4. 操作回数が奇数である照明の数をカウントする。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 入力を高速化するために sys.stdin.read を使用している。

• 差分配列のサイズは \(N+2\) として、\(R_j+1\) が範囲外参照にならないようにする。

• 最終的な判定は current % 2 == 1 で行い、奇数回操作された照明をカウントする。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    # 差分配列を用意
    diff = [0] * (N + 2)
    
    idx = 2
    for _ in range(M):
        L = int(data[idx])
        R = int(data[idx+1])
        idx += 2
        diff[L] += 1
        diff[R + 1] -= 1
    
    # 累積和を計算して各照明の操作回数を求める
    current = 0
    count = 0
    for i in range(1, N + 1):
        current += diff[i]
        if current % 2 == 1:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。