概要

この問題では、区間に対する反転操作を複数回行った後に、特定の点（会議室）が最終的にONになっているかを判定する必要があります。

考察

まず素朴な方法として、各操作ごとに区間 \([L, R]\) のすべての部屋の照明状態を更新することを考えますが、これは最大で \(N = 10^9\) に対して \(Q = 2 \times 10^5\) 回の操作があるため、全体で \(O(NQ)\) となり時間内に処理できません。

重要な観察は、「各部屋が何回反転されたか」だけが最終的な状態に関係するということです。つまり、偶数回反転されたらOFFのまま、奇数回ならONになります。

そこで、区間に対する加算処理を効率的に行う手法である imos法 を使います。imos法を使うことで、各区間への「+1」と「-1」のイベントを記録し、最後に累積和を取ることで各点での反転回数を求めることができます。

また、\(N\) が非常に大きいので、実際にすべての部屋を管理することは不可能です。しかし、注目すべきは会議室の位置 \(B_i\) と操作区間の端点 \(L_i, R_i+1\) のみです。そのため、これらの値に対して 座標圧縮 を行い、必要な点だけを扱うようにします。

まとめると： - 各操作は区間にフラグの反転回数を加算 → imos法で高速化 - 大きな \(N\) に対応するために座標圧縮を使用 - 最後に各会議室の位置を見て、そこでの反転回数が奇数かどうか判定すればOK

アルゴリズム

1. すべての操作区間 \([L_i, R_i]\) に対して、imos法のイベントとして \((L_i, +1),\ (R_i+1, -1)\) を登録します。
2. 登場する点（会議室の位置 \(B_i\) およびイベントの位置）を集めてソートし、それらに対して座標圧縮を行います。
3. imos法により、各圧縮後のインデックスにおける反転回数の累積和を計算します。
4. 各会議室 \(B_i\) について、その位置に対応する圧縮後のインデックスを求め、その地点での反転回数が奇数であれば点灯していると判断します。
5. 点灯している会議室の数をカウントして出力します。

例えば、操作が [1, 3] と [2, 4] で、会議室が 2 の場合： - イベント: (1,+1), (4,-1), (2,+1), (5,-1) - 圧縮後の点: [1,2,4,5] - imos配列処理後、位置2での反転回数は2回 → OFF

計算量

• 時間計算量: \(O((M + Q) \log (M + Q))\)
  • イベントのソートと座標圧縮が支配的
• 空間計算量: \(O(M + Q)\)
  • 座標リストやimos配列のサイズ

実装のポイント

• imos法を使うときは、区間の終わりの次に -1 を入れることを忘れない
• 座標圧縮時は set で重複を除いてからソートすると効率的
• 各会議室の位置に対応するインデックスを求める際は、bisect_right(points, b) - 1 を使うことで正確な場所を得られる

## ソースコード

```python
import sys
from bisect import bisect_left, bisect_right

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    
    B = list(map(int, data[idx:idx+M])); idx += M
    B.sort()
    
    # 座標圧縮のためのイベントリストを作成
    events = []
    for _ in range(Q):
        L = int(data[idx]); idx += 1
        R = int(data[idx]); idx += 1
        events.append((L, 1))
        events.append((R+1, -1))
    
    # 座標圧縮対象の点を収集
    points = set(B)
    for e in events:
        points.add(e[0])
    points = sorted(points)
    
    # 座標圧縮マップの作成
    point_to_idx = {p: i for i, p in enumerate(points)}
    
    # imos法による区間加算処理
    count = [0] * (len(points) + 1)
    for pos, delta in events:
        i = point_to_idx[pos]
        count[i] += delta
    
    # 累積和を計算して各ポイントでのフラグ反転回数を求める
    for i in range(1, len(count)):
        count[i] += count[i-1]
    
    # 各会議室について、それが点灯しているかどうかを判定
    ans = 0
    for b in B:
        i = bisect_right(points, b) - 1
        if count[i] % 2 == 1:
            ans += 1
            
    print(ans)

if __name__ == "__main__":
    main()

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