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$ 都不存在墙，则摧毁 $(i, C_q)$ 处的墙。 如果存在某个 $i \gt R_q$ 使得 $(i, C_q)$ 有墙且对所有 $R_q \lt k \lt i$ 都不存在墙，则摧毁 $(i, C_q)$ 处的墙。 如果存在某个 $j \lt C_q$ 使得 $(R_q, j)$ 有墙且对所有 $j \lt k \lt C_q$ 都不存在墙，则摧毁 $(R_q, j)$ 处的墙。 如果存在某个 $j \gt C_q$ 使得 $(R_q, j)$ 有墙且对所有 $C_q \lt k \lt j$ 都不存在墙，则摧毁 $(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

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 \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$ 所有输入值均为整数。处理查询的过程可以如下解释：

在第 1 次查询中，$(R_1, C_1) = (1, 2)$。$(1, 2)$ 有一面墙，所以摧毁了 $(1, 2)$ 的墙。 在第 2 次查询中，$(R_2, C_2) = (1, 2)$。$(1, 2)$ 没有墙，所以摧毁了 $(2,2),(1,1),(1,3)$，它们是从 $(1, 2)$ 向上、下、左、右 看时首次出现的墙。 在第 3 次查询中，$(R_3, C_3) = (1, 3)$。$(1, 3)$ 没有墙，所以摧毁了 $(2,3),(1,4)$，它们是从 $(1, 3)$ 向上、下、左、右 看时首次出现的墙。

处理完所有查询后，剩下两面墙，位于 $(2, 1)$ 和 $(2, 4)$。

标签: AtCoder|abc370D

来源

AtCoder|abc370D