AT_abc370_d [ABC370D] Cross Explosion

题目描述

有一个网格，网格中有 $H$ 行和 $W$ 列。让 $(i, j)$ 表示从上往下第 $i$ 行，从左往上第 $j$ 列的单元格。
最初，每个单元格中都有一面墙。
按照下面给出的顺序处理 $Q$ 个查询后，求剩余墙的数量。

在第 $q$ 次查询中，我们给出了两个整数 $R_q$ 和 $C_q$ 。
您在 $(R_q, C_q)$ 处放置了一枚炸弹来摧毁墙壁。结果会发生以下过程。

• 如果在 $(R_q, C_q)$ 处有一堵墙，则摧毁这堵墙并结束进程。
• 如果 $(R_q, C_q)$ 处没有墙壁，则摧毁从 $(R_q, C_q)$ 向上、向下、向左、向右观察时出现的第一面墙壁。更确切地说，以下四个过程是同时进行的：
  • 如果存在一个 $i \lt R_q$ ，使得在 $(i, C_q)$ 处有一堵墙，而在所有 $i \lt k \lt R_q$ 的 $(k, C_q)$ 处都没有墙，则摧毁 $(i, C_q)$ 处的墙。
  • 如果存在一个 $i \gt R_q$ ，使得在 $(i, C_q)$ 处有一堵墙，而在所有 $R_q \lt k \lt i$ 的 $(k, C_q)$ 处都没有墙，则破坏 $(i, C_q)$ 处的墙。
  • 如果存在一个 $j \lt C_q$ ，使得在所有 $j \lt k \lt C_q$ 中， $(R_q, j)$ 处有一堵墙，而 $(R_q, k)$ 处没有墙，则破坏 $(R_q, j)$ 处的墙。
  • 如果存在一个 $j \gt C_q$ ，使得在 $(R_q, j)$ 处有一堵墙，而在所有 $C_q \lt k \lt j$ 的 $(R_q, k)$ 处没有墙，则破坏 $(R_q, j)$ 处的墙。

输入格式

第一行 $3$ 个整数 $H,W,Q$。

接下来每行 $2$ 个整数 $R,C$，表示在坐标 $R,C$ 出放置了一枚炸弹。

输出格式

输出一个整数，表示最后剩下多少堵墙。

输入输出样例 #1

输入 #1

2 4 3
1 2
1 2
1 3

输出 #1

2

输入输出样例 #2

输入 #2

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

输出 #2

10

输入输出样例 #3

输入 #3

4 3 10
2 2
4 1
1 1
4 2
2 1
3 1
1 3
1 2
4 3
4 2

输出 #3

2

说明/提示

• $1 \leq H, W$
• $H \times W \leq 4 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq R_q \leq H$
• $1 \leq C_q \leq W$
• 所有输入值均为整数。

Translate by DeepL,Manually verified.