Chess Strikes Back (hard version)
Contest: Codeforces Round 657 (Div. 2)
Difficulty rating: 2800
Tags: data structures, divide and conquer

Note that the difference between easy and hard versions is that in hard version unavailable cells can become available again and in easy version can't. You can make hacks only if all versions are solved.

Ildar and Ivan are tired of chess, but they really like the chessboard, so they invented a new game. The field is a chessboard $$$2n \times 2m$$$: it has $$$2n$$$ rows, $$$2m$$$ columns, and the cell in row $$$i$$$ and column $$$j$$$ is colored white if $$$i+j$$$ is even, and is colored black otherwise.

The game proceeds as follows: Ildar marks some of the white cells of the chessboard as unavailable, and asks Ivan to place $$$n \times m$$$ kings on the remaining white cells in such way, so that there are no kings attacking each other. A king can attack another king if they are located in the adjacent cells, sharing an edge or a corner.

Ildar would like to explore different combinations of cells. Initially all cells are marked as available, and then he has $$$q$$$ queries. In each query he either marks a cell as unavailable, or marks the previously unavailable cell as available. After each query he would like to know whether it is possible to place the kings on the available cells in a desired way. Please help him!

Input format:
The first line of input contains three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \leq n, m, q \leq 200\,000$$$) — the size of the board and the number of queries.

$$$q$$$ lines follow, each of them contains a description of a query: two integers $$$i$$$ and $$$j$$$, denoting a white cell on the board ($$$1 \leq i \leq 2n$$$, $$$1 \leq j \leq 2m$$$, $$$i + j$$$ is even). If the cell $$$(i, j)$$$ was available before the query, then it becomes unavailable. Otherwise, if the cell was unavailable, it becomes available.

Output format:
Output $$$q$$$ lines, $$$i$$$-th line should contain answer for a board after $$$i$$$ queries of Ildar. This line should contain "YES" if it is possible to place the kings on the available cells in the desired way, or "NO" otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first example case after the second query only cells $$$(1, 1)$$$ and $$$(1, 5)$$$ are unavailable. Then Ivan can place three kings on cells $$$(2, 2)$$$, $$$(2, 4)$$$ and $$$(2, 6)$$$.

After the third query three cells $$$(1, 1)$$$, $$$(1, 5)$$$ and $$$(2, 4)$$$ are unavailable, so there remain only 3 available cells: $$$(2, 2)$$$, $$$(1, 3)$$$ and $$$(2, 6)$$$. Ivan can not put 3 kings on those cells, because kings on cells $$$(2, 2)$$$ and $$$(1, 3)$$$ attack each other, since these cells share a corner.

Example input:
1 3 3
1 1
1 5
2 4

Example output:
YES
YES
NO

Example input:
3 2 10
4 2
6 4
1 3
4 2
6 4
2 2
2 4
1 3
4 4
3 1

Example output:
YES
YES
NO
NO
YES
YES
NO
YES
YES
NO

Editorial:
Let's divide the grid into $$$nm$$$ squares of size $$$2 \times 2$$$. Each square contains exactly two white cells. So, we should put exactly one king into one square.
Let's mark a square L, if its left upper cell is banned and R if its right down cell is banned. Square can be L and R at the same time.
If there exists some L-square $$$(x_1, y_1)$$$ and R-square $$$(x_2, y_2)$$$, such that:
• $$$x_1 \leq x_2$$$
• $$$y_1 \leq y_2$$$
the answer is NO. It's easy to prove because if such pair of cells exists we can consider path from $$$(x_1, y_1)$$$ to $$$(x_2, y_2)$$$. In this path, there will be two neighboring cells.
If no such pairs of cells exist the answer is YES.
So, after each query, we should check this condition.
Let's maintain the values:
• $$$a_x = $$$ minimal $$$y$$$, such that $$$(x, y)$$$ is L-square
• $$$b_x = $$$ maximal $$$y$$$, such that $$$(x - 1, y)$$$ is R-square
These values can be maintained using $$$O(n)$$$ sets in $$$O(\log{q})$$$ time.
After that, we should check, that $$$a_i > b_j$$$ for all $$$i > j$$$.
Let's make a segment tree with values:
• minimal $$$a_i$$$ on segment
• maximal $$$b_i$$$ on segment
• the flag, that for all $$$i > j$$$ from the segment it is true, that $$$a_i > b_j$$$
It is easy to merge two such segments, to calculate the flag, we should check, that $$$min_{left} > max_{right}$$$.
So, the total time to answer the query is $$$O(\log{n}+\log{q})$$$.
Total complexity is $$$O((n+q)(\log{n}+\log{q}))$$$.