P12018 [NOISG 2025 Finals] 机器人

Funnyland 被建模为一个大小为 $(h + 2) \times (w + 2)$ 的网格。网格的行编号从 $0$ 到 $h + 1$（从上到下），列编号从 $0$ 到 $w + 1$（从左到右）。我们将位于网格第 $r$ 行、第 $c$ 列的单元格称为单元格 $(r, c)$。 最初，此网格中的所有单元格都被涂成 *白色*，除了最右侧的一列单元格，它们全部被涂成 *黑色*。 第 $1$ 到 $w$ 列中每列恰好包含一个特殊单元格。这些特殊单元格将被涂成 *红色* 或 *蓝色*。网格的边界（即最上方的行、最下方的行、最左侧的列和最右侧的列）永远不会包含特殊单元格。 一些机器人将被放置在最左侧的一列单元格中，并根据它们所在单元格的颜色进行移动： - 如果单元格是白色的，机器人向右移动。 - 如果单元格是红色的，机器人向上移动。 - 如果单元格是蓝色的，机器人向下移动。 - 如果单元格是黑色的，机器人不会移动。 机器人不会相互碰撞，每个机器人独立移动。多个机器人可以占据同一个单元格。 一次查询由两个整数 $a$ 和 $b$ 组成（$1 \leq a < b \leq h$）。对于每个 $a \leq c \leq b$，都会有一个机器人从 $(c, 0)$ 位置开始。在所有可能的特殊单元格红色或蓝色涂色方案中，确定机器人最终可能占据的不同单元格的最小数量。 请注意，不同的查询可能会导致不同的特殊单元格涂色方案。

无

无

### 子任务 对于所有测试用例，输入满足以下约束条件： - $1 \leq w, q \leq 200\,000$ - $2 \leq h \leq 200\,000$ - 对于所有 $1 \leq j \leq w$，有 $1 \leq x[j] \leq h$ - 对于所有 $1 \leq i \leq q$，有 $1 \leq a[i] < b[i] \leq h$ 你的程序将在满足以下特殊性质的输入数据上进行测试： | 子任务 | 分数 | 特殊性质 | | :-: | :-: | :-: | | $0$ | $0$ | 样例 | | $1$ | $10$ | $h, w \leq 16, q \leq 20$ | | $2$ | $4$ | $a[i] + 1 = b[i]$ | | $3$ | $12$ | $x[1] < x[2] < \cdots < x[w]$ | | $4$ | $43$ | $h, w, q \leq 5000$ | | $5$ | $31$ | 无 | ### 样例 1 解释 此样例适用于子任务 $1, 4, 5$。 网格的颜色如下，特殊单元格用紫色表示。  对于第一个查询，我们可以将 $(3, 1)$ 和 $(4, 3)$ 处的特殊单元格涂成蓝色，将 $(2, 2)$ 和 $(1, 4)$ 处的特殊单元格涂成红色，以获得以下效果：  - 从 $(1, 0)$ 开始的机器人移动到 $(1, 1), (1, 2), (1, 3), (1, 4), (0, 4), (0, 5)$，最终停在 $(0, 5)$。 - 从 $(2, 0)$ 开始的机器人移动到 $(2, 1), (2, 2), (1, 2), (1, 3), (1, 4), (0, 4), (0, 5)$，最终停在 $(0, 5)$。 - 从 $(3, 0)$ 开始的机器人移动到 $(3, 1), (4, 1), (4, 2), (4, 3), (5, 3), (5, 4)$，最终停在 $(5, 5)$。 - 从 $(4, 0)$ 开始的机器人移动到 $(4, 1), (4, 2), (4, 3), (5, 3), (5, 4)$，最终停在 $(5, 5)$。 机器人最终停在 $2$ 个不同的单元格 $(0, 5)$ 和 $(5, 5)$，因此正确的输出是 $2$。 对于第二个查询，我们可以按如下方式涂色：  从 $(1, 0), (2, 0)$ 和 $(3, 0)$ 开始的机器人最终都停在 $(0, 5)$。 对于第三个查询，我们可以按如下方式涂色：  从 $(2, 0), (3, 0)$ 和 $(4, 0)$ 开始的机器人最终都停在 $(3, 5)$。 ### 样例 2 解释 此样例适用于子任务 $1, 4, 5$。