← 返回题目列表

AtCoder · abc179_f

F. 简化黑白棋

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

分数: 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

每次查询后,网格都会按以下方式更改:

Figure


示例输入 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