この問題は俗にイベントソートと呼ばれる手法を用いて解くことができます。

会議室の番号を時刻に変換し、問題を次のように読み替えます。

問題：
照明が \(1\) つあり、時刻 \(0\) で消灯状態です。高橋君は時刻 \(L_i\) と \(R_i+1\) に合計 \(2Q\) 回の操作を行い、照明の状態を反転させます。時刻 \(B_1,\ldots,B_M\) のうち照明が点灯しているものの個数を求めてください

これは時刻順に操作をシミュレーションすることで求めることができます。このように、時刻順にシミュレーションを行う手法をイベントソートと呼びます。

特に今回の問題では、時刻 \(T\) で照明が点灯していることは時刻 \(T\) までに操作が奇数回行われたことと同値なので、「時刻 \(T\) までの操作回数は？」が求まれば十分です。これは \(2Q\) 回全ての操作の時刻をソートした配列を二分探索することで高速に求めることができます。

計算量は \(O((M+Q)\log Q)\) です。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, m, q;
  cin >> n >> m >> q;
  vector<int> b(m);
  for(int i=0; i<m; i++) cin >> b[i];

  vector<int> s;
  for(int i=0; i<q; i++){
    int l, r;
    cin >> l >> r;
    s.push_back(l);
    s.push_back(r+1);
  }
  sort(s.begin(), s.end());

  int ans = 0;
  for(int i=0; i<m; i++){
    int cnt = upper_bound(s.begin(), s.end(), b[i]) - s.begin();
    if(cnt % 2 == 1){
      ans++;
    }
  }
  cout << ans << endl;
}

実装例 (Python)

import bisect
N, M, Q = map(int, input().split())
B = list(map(int, input().split()))

s = []
for _ in range(Q):
  L, R = map(int, input().split())
  s.append(L)
  s.append(R+1)
s.sort()

ans = 0
for b in B:
  cnt = bisect.bisect_right(s, b)
  if cnt % 2 == 1:
    ans += 1
print(ans)