P14087 [ICPC 2023 Seoul R] Farm

有一块与一条直路相邻的农田，假设这条路位于 $x$ 轴上。农田的每条边都是水平或竖直的。最左边和最右边的边为竖直边，且均与位于路上的底边相连。底边的长度等于所有其他水平边长度之和。见图 C.1（a）。  在图 C.1 中，农田边界上或内部的小点表示害虫发生的位置。为有效防治虫害，农民试图将受害区域划分为若干个矩形区域，要求满足以下条件： - 每个矩形区域必须完全位于农田内。矩形的边可以重叠农田边界。 - 每个矩形的边必须是水平或竖直的。 - 各矩形区域完全分离，连边界也不能重叠。 - 每个害虫发生点必须被某个矩形区域覆盖。害虫发生点可以落在某个矩形区域的边上。 图 C.1（b）展示了用四个矩形区域覆盖所有发生点的方案。农民希望使覆盖害虫区域所用的矩形个数最少，以便高效地管理虫害。 现给你农田的边界和所有发生虫害的位置，请编程计算满足条件所需的最少矩形区域数。

输入以标准输入读入。第一行包含两个整数 $m$（$4 \leq m\leq 100,000$）和 $n$（$0\leq n\leq 100,000$），其中 $m$ 为农田边界边数，$n$ 为害虫发生点数量。第二行有 $m$ 个整数 $v_1, v_2, \dots, v_m$（$v_1 = v_m = 0, 0 \leq v_i \leq 10^6$），表示竖直边的 $x$ 坐标与水平边的 $y$ 坐标。在顺时针遍历农田上边界时，从底边左端点依次给出竖直和水平边的坐标。接下来 $n$ 行，每行两个整数 $x$ 和 $y$，表示一个害虫发生点的坐标 $(x, y)$，所有害虫点均在农田边界或内部。

输出一行，仅包含一个整数，表示满足条件所需的最少矩形区域数。

由 ChatGPT 5 翻译