AT_abc179_f [ABC179F] Simplified Reversi

题目描述

有一个纵向 $N$ 格、横向 $N$ 格的网格。第 $i$ 行第 $j$ 列的格子记作 $(i, j)$。

在网格中央的 $(N-2) \times (N-2)$ 个格子中，每个格子上都放有一颗黑色石子。在下边界和右边界共 $2N-1$ 个格子上，每个格子上都放有一颗白色石子。

现在给出 $Q$ 个查询，请按顺序处理。查询有两种类型，输入格式和内容如下：

• 1 x：在 $(1, x)$ 处放置一颗白色石子。然后，将从该位置向下直到遇到最近的白色石子之间的所有黑色石子替换为白色石子。
• 2 x：在 $(x, 1)$ 处放置一颗白色石子。然后，将从该位置向右直到遇到最近的白色石子之间的所有黑色石子替换为白色石子。

请在处理完所有 $Q$ 个查询后，输出网格上剩余的黑色石子的数量。

输入格式

输入以以下格式从标准输入读入。

$N$ $Q$
$Query_1$
$\vdots$
$Query_Q$

输出格式

请输出处理完所有 $Q$ 个查询后，网格上剩余的黑色石子的数量。

输入输出样例 #1

输入 #1

5 5
1 3
2 3
1 4
2 2
1 2

输出 #1

1

输入输出样例 #2

输入 #2

200000 0

输出 #2

39999200004

输入输出样例 #3

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

说明/提示

限制条件

• $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$
• 不会有重复的查询

样例解释 1

每次查询后，网格的变化如下图所示。

由 ChatGPT 4.1 翻译