CF1373G Pawns

给你一个由 $n$ 行 $n$ 列组成的国际象棋棋盘。行从下到上编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。第 $x$ 列第 $y$ 行的格子记作 $(x, y)$。此外，第 $k$ 列是特殊列。 初始时棋盘为空。接下来有 $m$ 次操作，每次操作会在棋盘上添加或移除一个兵。如果当前格子 $(x, y)$ 没有兵，则在该格子添加一个兵；否则移除该格子的兵。 当前棋盘是“好”的，当且仅当可以通过如下规则将所有兵移动到特殊列： - 位于 $(x, y)$ 的兵可以移动到 $(x, y+1)$、$(x-1, y+1)$ 或 $(x+1, y+1)$； - 可以进行任意多次这样的移动； - 兵不能移出棋盘之外； - 每个格子最多只能有一个兵。 当前棋盘不一定总是“好”的。为了解决这个问题，你可以在棋盘顶部添加新的行，即新行的编号为 $n+1, n+2, n+3, \dots$。 在每次 $m$ 次操作后，输出一个整数——为了使棋盘变为“好”的，最少需要添加的行数。

第一行包含三个整数 $n$、$k$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5; 1 \le k \le n$），分别表示棋盘的大小、特殊列的编号和操作次数。 接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$），表示操作的格子。如果该格子没有兵，则在该格子添加一个兵；否则移除该格子的兵。

每次操作后输出一个整数，表示为了使棋盘变为“好”的，最少需要添加的行数。

由 ChatGPT 4.1 翻译