分数: 400 点
问题陈述
有一个网格 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) 并且不存在墙 (k, C_q) 对于所有人 i \lt k \lt R_q,摧毁位于 (i, C_q).
- 如果存在 i \gt R_q 使得墙存在于 (i, C_q) 并且不存在墙 (k, C_q) 对于所有人 R_q \lt k \lt i,摧毁位于 (i, C_q).
- 如果存在 j \lt C_q 使得墙存在于 (R_q, j) 并且不存在墙 (R_q, k) 对于所有人 j \lt k \lt C_q,摧毁位于 (R_q, j).
- 如果存在 j \gt C_q 使得墙存在于 (R_q, j) 并且不存在墙 (R_q, k) 对于所有人 C_q \lt k \lt j,摧毁位于 (R_q, j).
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
H W Q R_1 C_1 R_2 C_2 \vdots R_Q C_Q
输出
处理所有查询后打印剩余墙壁的数量。
示例输入 1
2 4 3 1 2 1 2 1 3
示例输出 1
2
处理查询的过程可以解释如下:
- 在第一个查询中, (R_1, C_1) = (1, 2)。有一堵墙位于 (1, 2),所以墙在 (1, 2) 被摧毁。
- 在第二个查询中, (R_2, C_2) = (1, 2)。那里没有墙 (1, 2),所以墙壁在 (2,2),(1,1),(1,3),这是从上、下、左、右看时出现的第一堵墙 (1, 2),已被摧毁。
- 在第三个查询中, (R_3, C_3) = (1, 3)。那里没有墙 (1, 3),所以墙壁在 (2,3),(1,4),这是从上、下、左、右看时出现的第一堵墙 (1, 3),已被摧毁。
处理完所有查询后,还剩下两堵墙,位于 (2, 1) 和 (2, 4).
示例输入 2
5 5 5 3 3 3 3 3 2 2 2 1 2
示例输出 2
10
示例输入 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