分数: 600 点
问题陈述
有一个网格 N 行和 N 方格列。让 (i, j) 是位于 i从顶部开始的第行和 j左起第 列。
各中央 (N-2) \times (N-2) 网格中的方格上有一个黑色的石头。 每个 2N - 1 底部有一个方块,右侧有一个白色的石头。 给出了
Q 查询。我们要求您按顺序处理它们。 有两种查询。它们的输入格式和说明如下:
1 x: 将一块白色石头放在 (1, x)。之后,对于每颗黑子 (1, x) 以及如果你从 (1, x),将其替换为白色石头。2 x: 将一块白色石头放在 (x, 1)。之后,对于每颗黑子 (x, 1) 以及如果你从右边走的话你击中的第一颗白子 (x, 1),将其替换为白色石头。
全部处理完毕后,格子上还有多少个黑子 Q 疑问?
约束
- 3 \leq N \leq 2\times 10^5
- 0 \leq Q \leq \min(2N-4,2\times 10^5)
- 2 \leq x \leq N-1
- 查询是成对不同的。
输入
输入由标准输入按以下格式给出:
N Q Query_1 \vdots Query_Q
输出
打印处理完所有棋子后,网格上有多少个黑色棋子 Q 查询。
示例输入 1
5 5 1 3 2 3 1 4 2 2 1 2
示例输出 1
1
每次查询后,网格都会按以下方式更改:

示例输入 2
200000 0
示例输出 2
39999200004
示例输入 3
176527 15 1 81279 2 22308 2 133061 1 80744 2 44603 1 170938 2 139754 2 15220 1 172794 1 159290 2 156968 1 56426 2 77429 1 97459 2 71282
示例输出 3
31159505795