103703: [Atcoder]ABC370 D - Cross Explosion

Problem Statement

There is a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the cell at the $i$-th row from the top and $j$-th column from the left.
Initially, there is one wall in each cell.
After processing $Q$ queries explained below in the order they are given, find the number of remaining walls.

In the $q$-th query, you are given two integers $R_q$ and $C_q$.
You place a bomb at $(R_q, C_q)$ to destroy walls. As a result, the following process occurs.

• If there is a wall at $(R_q, C_q)$, destroy that wall and end the process.
• If there is no wall at $(R_q, C_q)$, destroy the first walls that appear when looking up, down, left, and right from $(R_q, C_q)$. More precisely, the following four processes occur simultaneously:
  • If there exists an $i \lt R_q$ such that a wall exists at $(i, C_q)$ and no wall exists at $(k, C_q)$ for all $i \lt k \lt R_q$, destroy the wall at $(i, C_q)$.
  • If there exists an $i \gt R_q$ such that a wall exists at $(i, C_q)$ and no wall exists at $(k, C_q)$ for all $R_q \lt k \lt i$, destroy the wall at $(i, C_q)$.
  • If there exists a $j \lt C_q$ such that a wall exists at $(R_q, j)$ and no wall exists at $(R_q, k)$ for all $j \lt k \lt C_q$, destroy the wall at $(R_q, j)$.
  • If there exists a $j \gt C_q$ such that a wall exists at $(R_q, j)$ and no wall exists at $(R_q, k)$ for all $C_q \lt k \lt j$, destroy the wall at $(R_q, j)$.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the number of remaining walls after processing all queries.

Sample Input 1

2 4 3
1 2
1 2
1 3

Sample Output 1

2

The process of handling the queries can be explained as follows:

• In the 1st query, $(R_1, C_1) = (1, 2)$. There is a wall at $(1, 2)$, so the wall at $(1, 2)$ is destroyed.
• In the 2nd query, $(R_2, C_2) = (1, 2)$. There is no wall at $(1, 2)$, so the walls at $(2,2),(1,1),(1,3)$, which are the first walls that appear when looking up, down, left, and right from $(1, 2)$, are destroyed.
• In the 3rd query, $(R_3, C_3) = (1, 3)$. There is no wall at $(1, 3)$, so the walls at $(2,3),(1,4)$, which are the first walls that appear when looking up, down, left, and right from $(1, 3)$, are destroyed.

After processing all queries, there are two remaining walls, at $(2, 1)$ and $(2, 4)$.

Sample Input 2

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

Sample Output 2

10

Sample Input 3

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

Sample Output 3

2

问题陈述

有一个有$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$使得在$(R_q, j)$处有一堵墙，并且对于所有$j \lt k \lt C_q$，$(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)$处的墙。

约束条件

• $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

处理查询的过程可以解释如下：

• 在第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