CF1379F2 Chess Strikes Back (hard version)

请注意，简单版和困难版的区别在于，困难版中不可用的格子可以再次变为可用，而简单版中则不行。只有在解决了所有版本后才能进行 Hack。 Ildar 和 Ivan 玩腻了国际象棋，但他们非常喜欢棋盘，于是发明了一种新游戏。棋盘为 $2n \times 2m$，共有 $2n$ 行、$2m$ 列。第 $i$ 行第 $j$ 列的格子，如果 $i+j$ 为偶数则为白色，否则为黑色。 游戏规则如下：Ildar 会将棋盘上的部分白色格子标记为不可用，然后让 Ivan 在剩下的可用白色格子上放置 $n \times m$ 个国王，使得任意两个国王不会互相攻击。国王可以攻击与其相邻的格子（包括共享边或角的格子）。 Ildar 想要探索不同的格子组合。初始时所有格子均为可用，之后他会进行 $q$ 次操作。每次操作，他要么将某个格子标记为不可用，要么将之前不可用的格子重新标记为可用。每次操作后，他都想知道是否可以在当前可用的格子上以要求的方式放置国王。请你帮助他！

输入的第一行包含三个整数 $n$、$m$、$q$（$1 \leq n, m, q \leq 200\,000$），表示棋盘的大小和操作次数。 接下来有 $q$ 行，每行描述一次操作，包含两个整数 $i$ 和 $j$，表示棋盘上的一个白色格子（$1 \leq i \leq 2n$，$1 \leq j \leq 2m$，且 $i+j$ 为偶数）。如果该格子在本次操作前是可用的，则变为不可用；否则，如果该格子在本次操作前是不可用的，则变为可用。

输出 $q$ 行，第 $i$ 行表示 Ildar 进行第 $i$ 次操作后棋盘的状态。如果可以在当前可用的格子上以要求的方式放置国王，则输出 "YES"；否则输出 "NO"。

在第一个样例中，第二次操作后，只有 $(1, 1)$ 和 $(1, 5)$ 两个格子不可用。此时 Ivan 可以将三个国王分别放在 $(2, 2)$、$(2, 4)$ 和 $(2, 6)$ 这三个格子上。 在第三次操作后，$(1, 1)$、$(1, 5)$ 和 $(2, 4)$ 三个格子不可用，剩下的可用格子只有 $(2, 2)$、$(1, 3)$ 和 $(2, 6)$。Ivan 无法将三个国王放在这些格子上，因为 $(2, 2)$ 和 $(1, 3)$ 这两个格子共享一个角，会互相攻击。 由 ChatGPT 4.1 翻译