E - Akari

得分：500分

问题描述

我们有一个$H$行$W$列的网格。网格中的方格$(i, j)$表示位于第$i$行第$j$列的方格。
在这个网格上有$N$个灯泡和$M$个障碍。第$i$个灯泡位于方格$(A_i, B_i)$，第$i$个障碍位于方格$(C_i, D_i)$。每个方格上最多只能放置一个物体，可以是灯泡或障碍。
每个灯泡会向四个方向发射光束 - 上、下、左、右 - 直到遇到一个障碍为止，照亮途中的方格。带有灯泡的方格也被视为照亮的方格。 在没有障碍的方格中，找到被灯泡照亮的方格的数量。

约束

• $1 \le H, W \le 1500$
• $1 \le N \le 5 \times 10^5$
• $1 \le M \le 10^5$
• $1 \le A_i \le H$
• $1 \le B_i \le W$
• $1 \le C_i \le H$
• $1 \le D_i \le W$
• $(A_i, B_i) \neq (A_j, B_j)\ \ (i \neq j)$
• $(C_i, D_i) \neq (C_j, D_j)\ \ (i \neq j)$
• $(A_i, B_i) \neq (C_j, D_j)$
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入给出：

$H$ $W$ $N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$A_3$ $B_3$

$\hspace{15pt} \vdots$

$A_N$ $B_N$

$C_1$ $D_1$

$C_2$ $D_2$

$C_3$ $D_3$

$\hspace{15pt} \vdots$

$C_M$ $D_M$

输出

按顺序输出被灯泡照亮的没有障碍方格的数量。

3 3 2 1
1 1
2 3
2 2

7

在没有障碍的方格中，除了方格$(3, 2)$，其他方格都被照亮。

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

8

在没有障碍的方格中，以下8个方格被照亮：

• 方格$(1, 1)$
• 方格$(1, 2)$
• 方格$(1, 3)$
• 方格$(1, 4)$
• 方格$(2, 2)$
• 方格$(3, 3)$
• 方格$(3, 4)$
• 方格$(4, 4)$

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

24

在这种情况下，所有没有障碍的方格都被照亮。