P13691 [CEOI 2025] highest

在一个平行宇宙中，Vlad 被困在了未来版的 Poenari 城堡中。该城堡共有 $n$ 层，编号为 $0$ 到 $n - 1$。在每一层 $i$（$0 \leq i \leq n - 1$），他只能向上移动：要么走楼梯，需要支付 $1$ 滴血（这是罗马尼亚吸血鬼使用的货币），要么变成蝙蝠通过通风口，这需要支付 $2$ 滴血。楼梯最多能将他向上带 $v[i]$ 层，而通风口最多能将他向上带 $w[i]$ 层。这里 $v$ 和 $w$ 是给定的两个数组：$v = v[0], v[1], \ldots, v[n - 1]$，$w = w[0], w[1], \ldots, w[n - 1]$。 形式化地说，在第 $i$ 层（$0 \leq i \leq n - 1$），Vlad 可以： * 以花费 $1$ 滴血的代价，从第 $i + 1$ 层到第 $i + v[i]$ 层的任意一层（不能超过 $n - 1$）。 * 以花费 $2$ 滴血的代价，从第 $i + 1$ 层到第 $i + w[i]$ 层的任意一层（不能超过 $n - 1$）。 此外，他的兄弟 Radu 和 Mircea 为 Vlad 提出了 $m$ 个场景，每个场景由两个楼层 $A$ 和 $B$ 构成（$A \leq B$）。Vlad 需要回答这 $m$ 个问题：从第 $A$ 层到第 $B$ 层，他最少需要牺牲多少滴血？

你需要实现以下函数： ```cpp std::vector solve(std::vector &v, std::vector &w, std::vector &queries); ``` * 接收数组 $v$（表示从每层出发的楼梯最大可上升的层数）和 $w$（表示从每层出发的通风口最大可上升的层数），它们的长度均为 $n$。 * 还接收 $m$ 个询问 queries，一个大小为 $m$ 的数组，每个元素是一个二元组 $(A, B)$，含义如上所述。 * 返回一个长度为 $m$ 的数组，包含每个询问的最少血滴消耗。

无

### 样例解释 1 考虑调用： ``` solve({2, 3, 1, 1, 1, 1, 2}, {3, 4, 1, 2, 1, 2, 2}, {{0, 4}, {0, 5}, {0, 6}}) ``` 此时 $n = 7$，有 $3$ 个询问，$v = [2, 3, 1, 1, 1, 1, 2]$，$w = [3, 4, 1, 2, 1, 2, 2]$。 对于第一个询问 $(0, 4)$，Vlad 需要两次花费 $1$ 滴血的跳跃：从 $0$ 到 $1$（虽然可以直接跳到 $2$，但从 $1$ 出发能走得更远），然后从 $1$ 到 $4$。总花费：$1 + 1 = 2$。 对于第二个询问 $(0, 5)$，有两条最优路径： 1. $0 \to 1$（花费 $1$），$1 \to 4$（花费 $1$），$4 \to 5$（花费 $1$）； 2. $0 \to 1$（花费 $1$），$1 \to 5$（花费 $2$）。 总花费分别为 $1 + 1 + 1 = 3$ 和 $1 + 2 = 3$。 对于第三个询问 $(0, 6)$，一种花费 $4$ 的路径是 $0 \to 1$（花费 $1$），$1 \to 5$（花费 $2$），$5 \to 6$（花费 $1$）。总花费：$1 + 2 + 1 = 4$。 因此函数应返回 $\{2, 3, 4\}$。 ### 样例解释 2 考虑调用： ``` solve({1, 1, 1, 2, 3, 2, 1, 1, 2, 3}, {2, 4, 1, 4, 1, 4, 1, 3, 2, 3}, {{3, 9}, {0, 9}, {0, 7}, {0, 4}, {3, 5}}) ``` 各个询问的最优路径如下： * $(3, 9)$：$3 \to 5$（花费 $1$），$5 \to 9$（花费 $2$）$\Rightarrow$ 总花费：$3$ * $(0, 9)$：$0 \to 1$（花费 $1$），$1 \to 5$（花费 $2$），$5 \to 9$（花费 $2$）$\Rightarrow$ 总花费：$5$ * $(0, 7)$：$0 \to 1$（花费 $1$），$1 \to 5$（花费 $2$），$5 \to 7$（花费 $1$）$\Rightarrow$ 总花费：$4$ * $(0, 4)$：$0 \to 1$（花费 $1$），$1 \to 4$（花费 $2$）$\Rightarrow$ 总花费：$3$ * $(3, 5)$：$3 \to 5$（花费 $1$）$\Rightarrow$ 总花费：$1$ 因此函数应返回 $\{3, 5, 4, 3, 1\}$。 ### 数据范围 * $1 \leq n, m \leq 500000$ * 对所有 $0 \leq i \leq n - 1$，$1 \leq v[i], w[i] \leq n$ * 对所有询问，$0 \leq A \leq B \leq n - 1$ ### 子任务 1. （5 分）$1 \leq n \leq 300, 1 \leq m \leq 500000$ 2. （7 分）$1 \leq n \leq 3000, 1 \leq m \leq 3000$ 3. （11 分）$1 \leq n \leq 20000, 1 \leq m \leq 20000$ 4. （44 分）$1 \leq n \leq 200000, 1 \leq m \leq 200000$ 5. （8 分）$1 \leq n \leq 500000, 1 \leq m \leq 500000$，且对于所有 $0 \leq i < j \leq n - 1$，$v[i] \leq v[j]$ 且 $w[i] \leq w[j]$ 6. （25 分）无额外限制 --- 翻译由 ChatGPT-5 完成