Simplified Reversi

题目描述

有一个由 $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$ 个查询后，网格上还有多少枚黑子？

输入格式

输入从标准输入给出，格式如下： $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

提示

$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$ 查询两两互不相同。每个查询后，网格按如下方式变化：

标签: AtCoder|abc179F

来源

AtCoder|abc179F