F - 简化版黑白棋

得分：600 分

问题描述

给定一个有 $N$ 行 $N$ 列方格的网格。设 $(i, j)$ 是位于从上往下数的第 $i$ 行、从左往右数的第 $j$ 列的方格。

网格中央的 $(N-2) \times (N-2)$ 个方格上有黑色棋子。 右边和下方的 $2N - 1$ 个方格上有白色棋子。

给出 $Q$ 个查询，需要按顺序进行处理。 查询有两种类型。它们的输入格式和描述如下：

• 1 x：在 $(1, x)$ 处放置一个白色棋子。然后，从 $(1, x)$ 向下方遇到的第一个白色棋子之前的每个黑色棋子都替换为白色棋子。
• 2 x：在 $(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$ 个查询后，网格上有多少个黑色棋子。

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

1

每次查询后，网格的变化如下：

200000 0

39999200004

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

31159505795