概要

各操作は区間 \([L,R]\) の照明を反転します。最終的に「会議室として指定された \(M\) 個の部屋」のうち、点灯している部屋数だけを求めます。

考察

• \(N \le 10^9\) と非常に大きいので、全部屋の状態を配列で持って反転するような方法（各操作で \(O(N)\)、あるいはビット配列でも \(N\) が大きすぎる）は不可能です。
• しかし、知りたいのは 会議室の部屋 \(B_1,\dots,B_M\) の状態だけ です。会議室以外の部屋がどうなっていても答えに影響しません。
• 各操作 \([L,R]\) に対して、「その区間に含まれる会議室の部屋」だけが反転されます。
  • 会議室の部屋番号配列 \(B\) をソートしておくと、区間 \([L,R]\) に含まれる会議室は 連続した添字範囲 になります。
  • その範囲を毎回ひとつずつ反転すると最悪 \(O(MQ)\) で間に合いません（\(2\times 10^5\) 同士で厳しい）。
• そこで「区間反転」をまとめて処理する定番として、差分配列（いもす法）を使います。ただし反転なので加算ではなく XOR（偶奇） で管理します。

例： - 会議室が \(B=[2,5,8,10]\)、操作が \([4,9]\) のとき、含まれる会議室は \(5,8\) なので添字で言うと \([1,2]\) を反転すればよい、と分かります。

アルゴリズム

1. 会議室の部屋番号配列 \(B\) を昇順にソートする。
2. 長さ \(M+1\) の配列 diff を用意し、会議室の「反転回数の偶奇」を差分で持つ（初期はすべて 0）。
3. 各操作 \([L,R]\) について：
   • l = lower_bound(B, L)：\(B[l] \ge L\) となる最小の添字
   • r = upper_bound(B, R) - 1：\(B[r] \le R\) となる最大の添字
   • もし l <= r なら、会議室の添字区間 \([l,r]\) が反転対象なので
     diff[l] ^= 1、diff[r+1] ^= 1 として差分に反転を記録する。
4. 最後に diff の前から累積 XOR（prefix XOR）を取り、
   • cur = その会議室が最終的に反転された回数の偶奇（0なら消灯、1なら点灯）
   • ans += cur として点灯数を数える。

この方法だと、各操作は二分探索2回＋差分更新だけで済みます。

計算量

• 時間計算量: \(O(M\log M + Q\log M + M)\)（支配的には \(O((M+Q)\log M)\)）
• 空間計算量: \(O(M)\)

実装のポイント

• bisect_left / bisect_right を使うと、区間 \([L,R]\) に入る会議室の添字範囲を高速に取れます。

  • r = bisect_right(B, R) - 1 として「\(R\) 以下の最後」を作るのがコツです。

• 該当する会議室が1つもない操作もあるので、必ず if l <= r: を入れます。

• 反転は「回数の偶奇」だけが重要なので、加算ではなく ^= 1（XOR）で管理します。

  ソースコード

import sys
from bisect import bisect_left, bisect_right

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    M = int(next(it))
    Q = int(next(it))

    B = [int(next(it)) for _ in range(M)]
    B.sort()

    diff = [0] * (M + 1)

    for _ in range(Q):
        L = int(next(it))
        R = int(next(it))
        l = bisect_left(B, L)
        r = bisect_right(B, R) - 1
        if l <= r:
            diff[l] ^= 1
            diff[r + 1] ^= 1

    cur = 0
    ans = 0
    for i in range(M):
        cur ^= diff[i]
        ans += cur

    print(ans)

if __name__ == "__main__":
    main()

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