← 返回题目列表

Codeforces · 1598/E

E. 楼梯

中文机器翻译题面 查看原题

给定一个矩阵,由 $$$n$$$ 行和 $$$m$$$ 列组成。行从上到下编号,列从左到右编号。

矩阵的每个单元格可以是空闲的或锁定的。

如果满足以下条件,我们将矩阵中的路径称为楼梯:

- 在空闲单元中开始和结束;
- 仅访问空闲单元格;
- 具有以下两个结构之一:第二个单元格位于第一个单元格右侧 $$$1$$$ 处,第三个单元格位于第二个单元格底部 $$$1$$$ 处,第四个单元格位于第三个单元格右侧 $$$1$$$ 处,依此类推; 第二个单元格距第一个单元格底部 $$$1$$$,第三个单元格距第二个单元格右侧 $$$1$$$,第四个单元格距第三个单元格底部 $$$1$$$,依此类推。

特别是,由单个单元格组成的路径被认为是楼梯。

以下是楼梯的一些示例:

最初矩阵的所有单元都是空闲的。

您必须处理 $$$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$$$ 查询后不同楼梯的数量。如果存在这样一个单元格,它出现在一条路径中而没有出现在另一条路径中,则认为两个楼梯是不同的。

示例

输入 #1

2 2 8
1 1
1 1
1 1
2 2
1 1
1 2
2 1
1 1

输出 #1

5
10
5
2
5
3
1
0

输入 #2

3 4 10
1 4
1 2
2 3
1 2
2 3
3 2
1 3
3 4
1 3
3 1

输出 #2

49
35
24
29
49
39
31
23
29
27

输入 #3

1000 1000 2
239 634
239 634

输出 #3

1332632508
1333333000