308915: CF1598E. Staircases

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Staircases

题意翻译

给定一个n*m的网格,每个格子为黑色或白色,初始时所有格子均为白色。 定义满足如下条件的路径为楼梯: * 起点和终点均为白色 * 路径上的所有点均为白色 * 满足以下两种结构之一 1.第二个格子在第一个格子右面,第三个格子在第二个格子下面,第四个格子在第三个格子右面,以此类推…… 2.第二个格子在第一个格子下面,第三个格子在第二个格子右面,第四个格子在第三个格子下面,以此类推…… 此外,一个单独的白色格子也被视为一个楼梯。 给定q个询问,每个询问给定整数x、y,并将格子(x,y)颜色翻转。 输出每次操作后网格中不同楼梯的个数(操作不独立)。

题目描述

You are given a matrix, consisting of $ n $ rows and $ m $ columns. The rows are numbered top to bottom, the columns are numbered left to right. Each cell of the matrix can be either free or locked. Let's call a path in the matrix a staircase if it: - starts and ends in the free cell; - visits only free cells; - has one of the two following structures: 1. the second cell is $ 1 $ to the right from the first one, the third cell is $ 1 $ to the bottom from the second one, the fourth cell is $ 1 $ to the right from the third one, and so on; 2. the second cell is $ 1 $ to the bottom from the first one, the third cell is $ 1 $ to the right from the second one, the fourth cell is $ 1 $ to the bottom from the third one, and so on. In particular, a path, consisting of a single cell, is considered to be a staircase. Here are some examples of staircases: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1598E/30e6b70a090f9657a06b957e8113944b3c2b16f3.png)Initially all the cells of the matrix are free. You have to process $ q $ queries, each of them flips the state of a single cell. So, if a cell is currently free, it makes it locked, and if a cell is currently locked, it makes it free. Print the number of different staircases after each query. Two staircases are considered different if there exists such a cell that appears in one path and doesn't appear in the other path.

输入输出格式

输入格式


The first line contains three integers $ n $ , $ m $ and $ q $ ( $ 1 \le n, m \le 1000 $ ; $ 1 \le q \le 10^4 $ ) — the sizes of the matrix and the number of queries. Each of the next $ q $ lines contains two integers $ x $ and $ y $ ( $ 1 \le x \le n $ ; $ 1 \le y \le m $ ) — the description of each query.

输出格式


Print $ q $ integers — the $ i $ -th value should be equal to the number of different staircases after $ i $ queries. Two staircases are considered different if there exists such a cell that appears in one path and doesn't appear in the other path.

输入输出样例

输入样例 #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

Input

题意翻译

给定一个n*m的网格,每个格子为黑色或白色,初始时所有格子均为白色。 定义满足如下条件的路径为楼梯: * 起点和终点均为白色 * 路径上的所有点均为白色 * 满足以下两种结构之一 1.第二个格子在第一个格子右面,第三个格子在第二个格子下面,第四个格子在第三个格子右面,以此类推…… 2.第二个格子在第一个格子下面,第三个格子在第二个格子右面,第四个格子在第三个格子下面,以此类推…… 此外,一个单独的白色格子也被视为一个楼梯。 给定q个询问,每个询问给定整数x、y,并将格子(x,y)颜色翻转。 输出每次操作后网格中不同楼梯的个数(操作不独立)。

加入题单

上一题 下一题 算法标签: