十字爆破

题目描述

有一个 $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$,$(k, C_q)$ 处都没有墙,则摧毁 $(i, C_q)$ 处的墙。
• 若存在 $i \gt R_q$,使得 $(i, C_q)$ 处有墙,且对所有满足 $R_q \lt k \lt i$ 的 $k$,$(k, C_q)$ 处都没有墙,则摧毁 $(i, C_q)$ 处的墙。
• 若存在 $j \lt C_q$,使得 $(R_q, j)$ 处有墙,且对所有满足 $j \lt k \lt C_q$ 的 $k$,$(R_q, k)$ 处都没有墙,则摧毁 $(R_q, j)$ 处的墙。
• 若存在 $j \gt C_q$,使得 $(R_q, j)$ 处有墙,且对所有满足 $C_q \lt k \lt j$ 的 $k$,$(R_q, k)$ 处都没有墙,则摧毁 $(R_q, j)$ 处的墙。

输入格式

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

$H$ $W$ $Q$
$R_1$ $C_1$
$R_2$ $C_2$
$\vdots$
$R_Q$ $C_Q$

输出格式

输出处理完所有查询后剩余的墙的数量。

样例

2 4 3
1 2
1 2
1 3

2

查询的处理过程如下:

第 1 个查询中,$(R_1, C_1) = (1, 2)$。$(1, 2)$ 处有墙,因此 $(1, 2)$ 处的墙被摧毁。

第 2 个查询中,$(R_2, C_2) = (1, 2)$。$(1, 2)$ 处没有墙,因此从 $(1, 2)$ 向上、下、左、右看最先出现的墙 $(2,2),(1,1),(1,3)$ 被摧毁。

第 3 个查询中,$(R_3, C_3) = (1, 3)$。$(1, 3)$ 处没有墙,因此从 $(1, 3)$ 向上、下、左、右看最先出现的墙 $(2,3),(1,4)$ 被摧毁。

处理完所有查询后,$(2, 1)$ 和 $(2, 4)$ 处还剩两堵墙。

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

10

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

2

数据范围

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