3733 - 棋盘
题目描述
小 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 行每行一个整数，表示在经过该次操作后，一共有多少个同颜色的联通区域。
样例
输入
3 3 1 2 2 3 1 2
输出
3 2 6
输入
100000 1 1 1
输出
9999900000
输入
15000 5 1 90 1 1231 1 91 1 1233 1 1232
输出
224970000 224940000 224940000 224910000 224940000
说明
【样例解释1】
初始棋盘白黑相间，第一次操作后有 3 个同颜色的联通区域，第二次操作后有 2 个同颜色的联通区域，第三次操作后有 6 个同颜色的联通区域。
【数据范围】
本题共有 10 个测试点，每个测试点 12 分
对于全部测试点：1 \le q, n \le 10^5, 1 \le opt[i] \le 2, 1 \le a[i] \le n
对于测试点 1-4：1 \le n \le 4, 1 \le q \le 10
对于测试点 5-6：1 \le n \le 10^5, q=1
对于测试点 7-9：1 \le n \le 10^5 , 保证同一个测试点所有的opt[i] 均相等
来源
2024常州市赛T7
标签
