AT_joi2014ho5 切り取り線 (Cutting)

JOI 君的爱好是纸艺制作。今天，JOI 君也打算制作一个纸艺作品。 首先，JOI 君按照设计图，在一张矩形纸上印上了 $N$ 条切割线。每条切割线都是与纸的边平行的线段。将纸按照所有切割线切开后得到的所有部分都会作为作品中的某个部件。当然，部件数量越多，制作就越困难。JOI 君想知道，按照所有切割线将纸切开后，纸会被分成多少个部分。

从标准输入读取以下数据。 - 第 $1$ 行包含三个整数 $W,\ H,\ N$，用空格隔开。$W$ 表示纸的横边长度，$H$ 表示纸的竖边长度，$N$ 表示切割线的数量。纸的左下、右下、左上、右上分别对应坐标 $(0, 0),\ (W, 0),\ (0, H),\ (W, H)$。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含四个整数 $A_i,\ B_i,\ C_i,\ D_i$（$0 \leq A_i \leq C_i \leq W$，$0 \leq B_i \leq D_i \leq H$），用空格隔开。表示第 $i$ 条切割线是连接 $(A_i, B_i)$ 和 $(C_i, D_i)$ 的线段。该线段与纸的某一边平行，即 $A_i = C_i$ 和 $B_i = D_i$ 中恰好有一个成立。此外，任意两条平行的切割线不会有公共点，任意一条切割线与平行的纸边也不会有公共点。

输出一个整数，表示纸被分成的部分数量。

## 任务 给定纸的大小和 $N$ 条切割线的信息，编写程序计算按照这些切割线切割后，纸被分成多少个部分。 ## 限制 所有输入数据满足以下条件。 - $1 \leq W \leq 1\,000\,000\,000$。 - $1 \leq H \leq 1\,000\,000\,000$。 - $1 \leq N \leq 100\,000$。 ## 子任务 ### 子任务 1 [5 分] 满足以下条件。 - $W \leq 1\,000$。 - $H \leq 1\,000$。 - $N \leq 1\,000$。 ### 子任务 2 [5 分] 满足以下条件。 - $N \leq 1\,000$。 ### 子任务 3 [20 分] 有公共点的不同两条切割线的组数不超过 $100\,000$。 ### 子任务 4 [20 分] 从任意一条切割线上的点出发，可以沿着若干切割线到达纸的某一边上的点。 ### 子任务 5 [50 分] 无额外限制。 ## 样例解释 1 对于该输入，切割线如下图所示。  因此，纸被切割线分成了 $4$ 个部分。该输入满足子任务 $4$ 的条件。 ## 样例解释 2 对于该输入，切割线如下图所示。  因此，纸被切割线分成了 $5$ 个部分。该输入不满足子任务 $4$ 的条件。 由 ChatGPT 4.1 翻译