AT_abc466_d [ABC466D] Placing Rooks

题目描述

有一个 $N$ 行 $N$ 列的棋盘。 初始时,方格上没有放置任何旗子。 从该状态开始,高桥君依次对方格进行 $M$ 次操作。第 $i$ 次操作 $1 \leq i \leq M)$ 如下: - 移除第 $R_i$ 行所有格子上放置的棋子。 - 接着,移除第 $C_i$ 列所有格子上放置的棋子。 - 最后,在第 $R_i$ 行第 $C_i$ 列的格子上放置一枚棋子。 请输出 $M$ 次操作后方格上剩余棋子的数量。

输入格式

第一行输入两个整数 $N$ 和 $M$,表示棋盘大小和操作数量。 接下来有 $M$ 行,每行两个整数 $R_i$ 和 $C_i$,表示一次操作。

输出格式

输出 $M$ 次操作后方格上棋子的数量。

说明/提示

### 样例解释 1 初始时 $3 \times 3$ 方格上什么都没有,经过各次操作后,棋子的移除和放置情况如下: (下面用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的格子) - 第 1 次操作:在 $(1,1)$ 放置棋子。 - 第 2 次操作:移除 $(1,1)$ 的棋子,在 $(1,2)$ 放置棋子。 - 第 3 次操作:在 $(3,3)$ 放置棋子。 - 第 4 次操作:移除 $(1,2)$ 和 $(3,3)$ 的棋子,在 $(3,2)$ 放置棋子。 - 第 5 次操作:在 $(1,3)$ 放置棋子。 - 第 6 次操作:移除 \((1,3)\) 的棋子,再次在 \((1,3)\) 放置棋子。 最终状态中,$(1,3)$ 和 $(3,2)$ 各有一枚棋子,因此输出 2。 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT_abc466_d/5debbd0faa8dfad83c6d9bc231b7f2f3f29711c66d81a3d87a2b9681fc69cf90.png) --- ### 约束条件 - $ 1 \leq N \leq 3\times 10^5 $ - $ 1 \leq M \leq 3\times 10^5 $ - $ 1 \leq R_i \leq N $ - $ 1 \leq C_i \leq N $ - 输入均为整数 (本题由 deepseek 翻译)