CF1598E Staircases

给定一个由 $n$ 行 $m$ 列组成的矩阵。行从上到下编号，列从左到右编号。 矩阵中的每个格子可以是“空闲”或“锁定”状态。 我们称矩阵中的一条路径为“楼梯路径”，如果它满足以下条件： - 路径的起点和终点都是空闲格子； - 路径只经过空闲格子； - 路径有以下两种结构之一： 1. 第二个格子在第一个格子的右边一格，第三个格子在第二个格子的下边一格，第四个格子在第三个格子的右边一格，依此类推； 2. 第二个格子在第一个格子的下边一格，第三个格子在第二个格子的右边一格，第四个格子在第三个格子的下边一格，依此类推。 特别地，只包含一个格子的路径也被认为是楼梯路径。 下面是一些楼梯路径的示例：  初始时，矩阵中的所有格子都是空闲的。 你需要处理 $q$ 个操作，每个操作会翻转一个格子的状态。如果该格子当前为空闲，则变为锁定；如果当前为锁定，则变为空闲。 每次操作后，输出当前矩阵中不同楼梯路径的数量。如果存在某个格子只出现在一条路径中而不出现在另一条路径中，则这两条路径被认为是不同的。

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n, m \le 1000$；$1 \le q \le 10^4$），分别表示矩阵的行数、列数和操作数。 接下来的 $q$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x \le n$；$1 \le y \le m$），表示每次操作的位置。

输出 $q$ 个整数，第 $i$ 个整数表示第 $i$ 次操作后不同楼梯路径的数量。如果存在某个格子只出现在一条路径中而不出现在另一条路径中，则这两条路径被认为是不同的。

由 ChatGPT 4.1 翻译