P6256 [ICPC 2019 WF] Directing Rainfall

波尔图和附近的杜罗河谷因生产波特酒而闻名。来自世界各地的葡萄酒爱好者来到这里品尝这种甜美的葡萄酒。国际波特酒鉴赏家联盟（ICPC）正在组织到杜罗河上游葡萄园的旅行。为了让游客的参观更加愉快，ICPC 最近在葡萄园上方安装了遮阳篷。这些遮阳篷保护游客在葡萄藤间漫步和品尝陈年波特酒时不被晒伤。 不幸的是，遮阳篷存在一个小问题。葡萄需要阳光和水才能生长。虽然遮阳篷能透过足够的阳光，但它们完全防水。这意味着雨水可能无法到达下方的葡萄园。如果不采取措施，今年的葡萄酒收成将岌岌可危！ ICPC 想通过在遮阳篷上打孔来解决这个问题，以便雨水能透过遮阳篷到达下方的葡萄园。由于雨季即将到来，时间紧迫，ICPC 希望以最少的打孔次数实现这一目标。我们将考虑这个问题的二维版本。需要浇灌的葡萄园是 $x$ 轴上的一个区间，遮阳篷被建模为 $x$ 轴上方的线段。遮阳篷是倾斜的，即不平行于 $x$ 轴或 $y$ 轴（参见图 F.1 了解示例）。雨水从无限高处直线下落。当雨水落在遮阳篷上时，它会流向遮阳篷的低端并从那里落下，除非在雨水落下的地方和遮阳篷的低端之间有一个孔——在这种情况下，雨水将通过孔落下。雨水从遮阳篷上落下后，继续垂直下落。 这种情况会重复，直到雨水落到地面（$x$ 轴）上。 出于法律原因，您必须确保至少有一些雨水是直接从葡萄园上方落到葡萄园的。这是为了防止任何葡萄园从邻近的葡萄园窃取所有的雨水（参见第二个样例输入了解示例）。

输入的第一行包含三个整数 $l$、$r$ 和 $n$，其中 $(l,r)$ $(0 \leq l < r \leq 10^9)$ 是表示葡萄园的区间，$n$ $(0 \leq n \leq 5 \times 10^5)$ 是遮阳篷的数量。接下来的 $n$ 行中的每一行描述一个遮阳篷，包含四个整数 $x_1, y_1, x_2, y_2$，其中 $(x_1, y_1)$ 是遮阳篷低端的位置，$(x_2, y_2)$ 是高端的位置 $(0 \leq x_1, x_2 \leq 10^9, x_1 eq x_2, $ 且 $ 0 < y_1 < y_2 \leq 10^9)$。 输入中给出的 $x$ 坐标（$l$、$r$ 以及所有遮阳篷的 $x_1$ 和 $x_2$ 的值）都是不同的。输入中描述的遮阳篷不会相交，且没有遮阳篷的端点会位于另一个遮阳篷上。

输出需要打孔的最小次数，以便从葡萄园上方落下的雨水能够到达葡萄园。

来源：ICPC 世界总决赛 2019 问题 F：引导降雨。 题面翻译由 ChatGPT-4o 提供。