放置棋子(Placing Rooks)

题目描述

有一个 $N$ 行 $N$ 列的网格，初始时没有棋子。

高桥进行 $M$ 次操作。第 $i$ 次操作如下：

1. 移除第 $R_i$ 行上的所有棋子
2. 移除第 $C_i$ 列上的所有棋子
3. 在格子 $(R_i, C_i)$ 放置一个棋子

求 $M$ 次操作后网格上棋子的数量。

输入格式

输入从标准输入按以下格式给出：

N M
R_1 C_1
R_2 C_2
\vdots
R_M C_M

输出格式

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

样例输入 #1

3 6
1 1
1 2
3 3
3 2
1 3
1 3

样例输出 #1

2

操作过程如下：

• 操作1：清第1行和第1列，放(1,1) → 棋子: (1,1)
• 操作2：清第1行和第2列，放(1,2) → 棋子: (1,2), (3,3)
• 操作3：清第3行和第3列，放(3,3) → 棋子: (1,2), (3,3)
• 操作4：清第3行和第2列，放(3,2) → 棋子: (1,2), (3,2) — 注意(1,2)被清第2列移除但(1,2)之前在第1行，不在第2列... 实际上清第2列会移除(1,2)，然后放(3,2) → 棋子: (3,3), (3,2)... 需重新审视

更详细的操作过程：

• 操作1：清第1行(无)、清第1列(无)，放(1,1) → {(1,1)}
• 操作2：清第1行(移除(1,1))、清第2列(无)，放(1,2) → {(1,2)}
• 操作3：清第3行(无)、清第3列(无)，放(3,3) → {(1,2), (3,3)}
• 操作4：清第3行(移除(3,3))、清第2列(移除(1,2))，放(3,2) → {(3,2)}
• 操作5：清第1行(无)、清第3列(无)，放(1,3) → {(3,2), (1,3)}
• 操作6：清第1行(移除(1,3))、清第3列(无)，放(1,3) → {(3,2), (1,3)}

最终棋子数：2

样例输入 #2

2 3
1 2
2 1
1 1

样例输出 #2

1

• 操作1：放(1,2) → {(1,2)}
• 操作2：清第2行(无)、清第1列(无)，放(2,1) → {(1,2), (2,1)}
• 操作3：清第1行(移除(1,2))、清第1列(移除(2,1))，放(1,1) → {(1,1)}

最终棋子数：1

数据范围

• $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$
• 所有输入为整数

知识点与难度

本题涉及的知识点从属于 GESP 四级，难度等级：⭐⭐。

测试点分布