概要

区間 \([L_j, R_j]\) の照明を「反転（ON/OFF切り替え）」する操作を \(M\) 回行ったあと、最終的に点灯している照明の個数を求めます。

考察

各操作は区間内の全要素を反転するので、素朴に「区間の全てを1つずつ反転」すると、最悪で \(O(NM)\) 近くになり（例：長い区間を何度も反転）、\(N \le 10^6, M \le 2\times10^5\) では確実に間に合いません。

重要な観察は次の2点です。

• ある照明 \(i\) が最終的に点灯するかどうかは、「その照明が反転された回数の偶奇」だけで決まる
  
  • 反転回数が偶数回 → 元のまま（消灯）
  • 反転回数が奇数回 → 反転されて点灯
• 区間加算（ここでは「区間反転の回数を数える」）は、差分配列（いわゆるいもす法）で高速に処理できる
  今回は「回数」を正確に数える必要はなく偶奇だけ欲しいので、加算の代わりに \(0/1\) の XOR（\(\oplus\)）で管理できます。

具体例： - \(N=5\)、操作が \([2,4]\)、\([3,5]\) の2回だとします。 - 反転回数（偶奇）は位置ごとに
1:0回, 2:1回, 3:2回, 4:2回, 5:1回
- 奇数回の 2 と 5 だけが最終的に点灯 → 答えは2

この「偶奇の累積」を差分で作れば、全体を \(O(N+M)\) で解けます。

アルゴリズム

差分配列 diff を用意し、区間反転 \([L, R]\) を次の更新で表現します。

• diff[L] を反転（diff[L] ^= 1）
• diff[R+1] を反転（diff[R+1] ^= 1）

その後、左から順に累積 XOR を取り、各位置が最終的に点灯しているか（=累積値が1か）を数えます。

• cur = 現在位置までの累積（偶奇）
• 各 \(i=1..N\) について
  
  • cur ^= diff[i]（ここまでの反転回数の偶奇）
  • cur == 1 なら照明 \(i\) は点灯 → カウントに加える

なぜこれで区間反転が表現できるか： - diff[L] で「ここから反転状態を切り替える」 - diff[R+1] で「ここで反転状態を元に戻す」 - 累積 XOR を取ると、\(L\) から \(R\) の間だけ cur が反転した状態になる

計算量

• 時間計算量: \(O(N + M)\)
  （差分更新が \(M\) 回、最後に \(1..N\) を1回走査）
• 空間計算量: \(O(N)\)
  （差分配列 diff が長さ \(N\) 程度）

実装のポイント

• 反転は偶奇だけ分かればよいので、差分配列は bytearray（0/1）で十分です（メモリ効率が良い）。

• R+1 にアクセスするため、配列は N+2 以上の長さを確保します（コードでは N+3）。

• 入力が大きいので、sys.stdin.buffer.read() で一括読み取りして高速に整数パースしています（Pythonでは重要な高速化ポイント）。

  ソースコード

import sys

def ints():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        sign = 1
        if data[i] == 45:  # '-'
            sign = -1
            i += 1
        x = 0
        while i < n and data[i] > 32:
            x = x * 10 + (data[i] - 48)
            i += 1
        yield sign * x

it = ints()
N = next(it)
M = next(it)

diff = bytearray(N + 3)
for _ in range(M):
    L = next(it)
    R = next(it)
    diff[L] ^= 1
    diff[R + 1] ^= 1

cur = 0
cnt = 0
for i in range(1, N + 1):
    cur ^= diff[i]
    cnt += cur

sys.stdout.write(str(cnt))

---

この解説は gpt-5.2-high によって生成されました。