概要

\(N\) 個の部屋（初期状態は消灯）に対し、指定された範囲 \([L, R]\) の照明を反転させる操作を \(Q\) 回行います。最終的に、指定された \(M\) 個の会議室のうち、何個の部屋が点灯しているかを求める問題です。

考察

1. 制約の確認

部屋の数 \(N\) が最大 \(10^9\) と非常に大きいため、すべての部屋の状態を配列などで管理することは不可能です。一方で、操作回数 \(Q\) と会議室の数 \(M\) は \(2 \times 10^5\) 程度であり、これらに注目した解法を考える必要があります。

2. 点灯・消灯の条件

ある部屋 \(x\) が最終的に点灯しているかどうかは、「その部屋 \(x\) が何回の反転操作（範囲 \([L, R]\)）に含まれたか」によって決まります。 - 操作回数が 奇数回：点灯 - 操作回数が 偶数回：消灯

したがって、各会議室 \(B_i\) について、その番号をカバーする操作 \([L_j, R_j]\) がいくつあるかを効率よく数えることがポイントになります。

3. 操作範囲の数え上げ

部屋 \(x\) が範囲 \([L, R]\) に含まれる条件は、\(L \leq x \leq R\) です。 これを変形すると、以下の \(2\) つの条件を同時に満たすことと同じです。 1. 範囲の始点 \(L\) が \(x\) 以下である（\(L \leq x\)） 2. 範囲の終点 \(R\) が \(x\) 以上である（\(R \geq x\)）

すべての操作の始点の集合を \(\mathcal{L}\)、終点の集合を \(\mathcal{R}\) としたとき、部屋 \(x\) を含む操作の個数は以下のように計算できます。 - ( \(L \leq x\) を満たす操作の数 ) \(-\) ( \(R < x\) を満たす操作の数 )

なぜなら、始点が \(x\) 以下である操作のうち、終点が \(x\) より手前（\(x\) 未満）で終わってしまっているものは、部屋 \(x\) をカバーしていないからです。

アルゴリズム

二分探索を用いて、各会議室ごとに操作回数を高速に求めます。

1. 全ての操作の始点 \(L_i\) をリスト l_coords に、終点 \(R_i\) をリスト r_coords に格納します。
2. 二分探索を行うために、l_coords と r_coords を昇順にソートします。
3. 各会議室 \(B_i\) について以下を行います：
   • bisect_right を用いて、l_coords の中で \(B_i\) 以下の値がいくつあるか（\(L \leq B_i\) の個数）を求めます。
   • bisect_left を用いて、r_coords の中で \(B_i\) より小さい値がいくつあるか（\(R < B_i\) の個数）を求めます。
   • \(2\) つの数の差を計算し、それが奇数ならカウントを \(1\) 増やします。
4. 最終的なカウントを出力します。

計算量

• 時間計算量: \(O((Q + M) \log Q)\)
  • 操作範囲のソートに \(O(Q \log Q)\)
  • 各会議室（\(M\) 個）に対して二分探索を行うのに \(O(M \log Q)\) かかります。
• 空間計算量: \(O(M + Q)\)
  • 会議室のリストおよび操作範囲のリストを保持するために必要です。

実装のポイント

• 高速な入出力: \(M\) や \(Q\) が大きいため、Python では sys.stdin.read().split() や sys.stdout.write を使用することで実行時間を短縮できます。

• 二分探索の使い分け:

  • bisect_right(list, x): \(x\) 以下の要素の数を数えるのに適しています（挿入位置の右側を返すため）。

  • bisect_left(list, x): \(x\) 未満の要素の数を数えるのに適しています（挿入位置の左側を返すため）。

    ソースコード

import sys
from bisect import bisect_left, bisect_right

def main():
    # 全ての入力を一度に読み込んでスペースで分割し、リスト化します。
    # この方法はPythonにおいて大量の数値を読み込む際に効率的です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 部屋の総数, M: 会議室の個数, Q: 操作の回数
    # Nは最大10^9、MとQは最大2*10^5です。
    n = int(input_data[0])
    m = int(input_data[1])
    q = int(input_data[2])
    
    # B: 会議室の部屋番号のリスト
    b = list(map(int, input_data[3:3+m]))
    
    # 各操作の範囲 [L, R] の始点 L と終点 R を別々のリストに格納します。
    l_coords = [0] * q
    r_coords = [0] * q
    
    current_idx = 3 + m
    for i in range(q):
        l_coords[i] = int(input_data[current_idx])
        r_coords[i] = int(input_data[current_idx + 1])
        current_idx += 2
        
    # 二分探索を用いるため、LとRのリストをソートします。
    l_coords.sort()
    r_coords.sort()
    
    lit_count = 0
    # 各会議室について、いくつの操作範囲に含まれているかを計算します。
    # 部屋 x が範囲 [L, R] に含まれる条件は L <= x かつ R >= x です。
    for pos in b:
        # count_l: 始点 L が会議室の番号 pos 以下である操作の数
        count_l = bisect_right(l_coords, pos)
        # count_r: 終点 R が会議室の番号 pos より小さい（posの手前で終わっている）操作の数
        count_r = bisect_left(r_coords, pos)
        
        # 会議室 pos を含む操作の総数は (count_l - count_r) となります。
        # 操作回数が奇数であれば、その部屋の照明は最終的に「点灯」状態になります。
        if (count_l - count_r) % 2 == 1:
            lit_count += 1
            
    # 会議室のうち点灯している部屋の個数を出力します。
    sys.stdout.write(str(lit_count) + '\n')

if __name__ == '__main__':
    main()

---

この解説は gemini-3-flash-preview によって生成されました。