概要

\(N\) 個の照明に対して \(M\) 回の区間トグル操作を行った後、点灯している照明の個数を求める問題です。いもす法（差分配列） を用いることで効率的に解くことができます。

考察

素朴なアプローチとその問題点

最も単純な方法は、各操作ごとに区間 \([L_j, R_j]\) のすべての照明を1つずつ切り替えることです。しかし、この方法では1回の操作に最大 \(O(N)\) の時間がかかり、全体で \(O(NM)\) となります。\(N\) が最大 \(10^6\)、\(M\) が最大 \(2 \times 10^5\) なので、最悪 \(2 \times 10^{11}\) 回の処理が必要になり、TLE（時間超過） になります。

重要な気づき

各照明 \(i\) について、最終的に点灯しているかどうかは、その照明が何回トグルされたか だけで決まります。

• トグル回数が 奇数 → 点灯
• トグル回数が 偶数 → 消灯

つまり、各照明のトグル回数を効率的に求められればよいのです。

いもす法による高速化

区間 \([L, R]\) に一律に \(+1\) する操作を高速に処理するテクニックとして いもす法（差分配列） があります。

差分配列 \(\text{diff}\) を用意し、区間 \([L, R]\) への加算を以下の2つの操作で表現します：

• \(\text{diff}[L] += 1\)
• \(\text{diff}[R+1] -= 1\)

すべての操作を処理した後、差分配列の 累積和 を取ると、各照明のトグル回数が得られます。

具体例

\(N = 5\), \(M = 2\), 操作が \([2, 4]\) と \([3, 5]\) の場合：

操作	diff[1]	diff[2]	diff[3]	diff[4]	diff[5]	diff[6]
初期	0	0	0	0	0	0
\([2,4]\)	0	+1	0	0	-1	0
\([3,5]\)	0	+1	+1	0	-1	-1

累積和を取ると：

照明	1	2	3	4	5
トグル回数	0	1	2	2	1

奇数回トグルされた照明は \(2\) と \(5\) なので、答えは 2 です。

アルゴリズム

1. サイズ \(N+2\) の差分配列 \(\text{diff}\) を \(0\) で初期化する
2. 各操作 \((L_j, R_j)\) に対して：
   • \(\text{diff}[L_j] += 1\)
   • \(\text{diff}[R_j + 1] -= 1\)
3. \(\text{diff}\) の累積和を取りながら、各照明 \(i\)（\(1 \leq i \leq N\)）のトグル回数を求める
4. トグル回数が奇数の照明の個数を数えて出力する

計算量

• 時間計算量: \(O(N + M)\)
  • 差分配列への書き込みが \(O(M)\)、累積和の計算とカウントが \(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列のサイズ

実装のポイント

• 差分配列のサイズを \(N+2\) にすることで、\(R+1 = N+1\) の場合でも配列外アクセスを防げます

• sys.stdin.buffer.read() で入力を一括読み込みすることで、Python でも高速に入力処理ができます

• 累積和を変数 current で管理し、配列を別途作らずにカウントすることでメモリ効率も良くなります

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    diff = [0] * (N + 2)
    
    for _ in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        diff[L] += 1
        diff[R + 1] -= 1
    
    count = 0
    current = 0
    for i in range(1, N + 1):
        current += diff[i]
        if current % 2 == 1:
            count += 1
    
    print(count)

main()

---

この解説は claude4.6opus-thinking によって生成されました。