← 返回题目
题库练习 棋盘
← 上一题 下一题 →

A71608 | 棋盘

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

小 Y 有一个 n \times n 棋盘，开始时这个棋盘每个格子的颜色是白黑相间的，即第一行的第 1,3,5……个格子是白色，第 2,4,6……个格子是黑色，第二行第 2,4,6……个格子是白色，第 1,3,5……个格子是黑色，如下图所示。

小 Y 会进行 q 次操作，每次操作会将某一行或者某一列的所有格子的颜色反转，即白色格子变成黑色格子，黑色格子变成白色格子。小 Y 想知道，在每次操作之后，一共有多少个同颜色(全黑或全白)的联通区域。这里联通指的是四联通，即两个格子之间有边相邻才算联通。

输入格式

第一行 2 个正整数 n，q，表示棋盘的大小和操作的次数。

第 2 到 q+1 行每行 2 个正整数 opt[i]，a[i]，若 opt[i] 为 1 则表示反转的是行，为 2 则表示反转的是列，a[i] 表示反转的是第几行/列。

输出格式

输出 q 行每行一个整数，表示在经过该次操作后，一共有多少个同颜色的联通区域。

输入输出样例

输入 #1
3 3
1 2
2 3
1 2
输出 #1
3
2
6
输入 #2
100000 1
1 1
输出 #2
9999900000
输入 #3
15000 5
1 90
1 1231
1 91
1 1233
1 1232
输出 #3
224970000
224940000
224940000
224910000
224940000
C++ 编辑器
输入
输出