Overview

Each operation toggles (flips) the lights in the interval \([L,R]\). We need to find how many of the \(M\) rooms designated as “meeting rooms” are lit at the end.

Analysis

• Since \(N \le 10^9\) is very large, it is impossible to maintain the state of all rooms in an array and flip them (each operation would be \(O(N)\), and even a bit array would be too large for such \(N\)).
• However, we only need to know the states of the meeting rooms \(B_1,\dots,B_M\). The states of non-meeting rooms do not affect the answer.
• For each operation \([L,R]\), only the “meeting rooms contained in that interval” are toggled.
  • If we sort the meeting room number array \(B\), the meeting rooms contained in interval \([L,R]\) form a contiguous range of indices.
  • Flipping them one by one each time would be \(O(MQ)\) in the worst case, which is too slow (both up to \(2\times 10^5\)).
• Therefore, we use the classic technique for batch interval flipping: a difference array (imos method). However, since we are flipping (toggling), we manage it with XOR (parity) instead of addition.

Example: - If the meeting rooms are \(B=[2,5,8,10]\) and the operation is \([4,9]\), the contained meeting rooms are \(5,8\), which correspond to index range \([1,2]\) that needs to be flipped.

Algorithm

1. Sort the meeting room number array \(B\) in ascending order.
2. Prepare an array diff of length \(M+1\) to hold the “parity of the number of flips” for meeting rooms as differences (initially all 0).
3. For each operation \([L,R]\):
   • l = lower_bound(B, L): the smallest index such that \(B[l] \ge L\)
   • r = upper_bound(B, R) - 1: the largest index such that \(B[r] \le R\)
   • If l <= r, then the meeting room index range \([l,r]\) is the flip target, so record the flip in the difference array as diff[l] ^= 1 and diff[r+1] ^= 1.
4. Finally, compute the prefix XOR of diff from the beginning:
   • cur = the parity of the total number of flips for that meeting room (0 means off, 1 means on)
   • Count the number of lit rooms with ans += cur.

With this method, each operation only requires two binary searches and a difference array update.

Complexity

• Time complexity: \(O(M\log M + Q\log M + M)\) (dominated by \(O((M+Q)\log M)\))
• Space complexity: \(O(M)\)

Implementation Notes

• Using bisect_left / bisect_right, you can quickly find the index range of meeting rooms within the interval \([L,R]\).

  • The trick is to compute r = bisect_right(B, R) - 1 to get “the last index that is \(\le R\)”.

• Some operations may not contain any meeting rooms, so always include the check if l <= r:.

• Since only the “parity of the number of flips” matters, we manage it with ^= 1 (XOR) instead of addition.

  Source Code

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()

This editorial was generated by gpt-5.2-high.