注意事项

请在提交源代码前添加 #include "highest.h"。

题目描述

在一个平行宇宙中，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 可以：

• 到达从楼层 $i+1$ 到楼层 $i+v[i]$ 的任意位置，不超过 $n-1$，费用为 $1$
• 到达从楼层 $i+1$ 到楼层 $i+w[i]$ 的任意位置，不超过 $n-1$，费用为 $2$

此外，他的兄弟 Radu 和 Mircea 为 Vlad 提出了 $m$ 个场景，每个场景包含两个楼层 $A$ 和 $B$ $(A \leq B)$。Vlad 必须回答他们的 $m$ 个问题：从楼层 $A$ 到楼层 $B$ 需要牺牲的最少血量是多少？

实现细节

你需要实现函数 solve：

std::vector<int> solve(std::vector<int> &v, std::vector<int> &w,
    std::vector<std::pair<int,int>> &queries);

• 接收向量 $v$，楼梯的高度，以及 $w$，每个楼层起始的通风系统高度，两个向量的大小均为 $n$。
• 还接收 queries，一个大小为 $m$ 的 pair 向量。每个 pair 包含题目描述中的 $A$ 和 $B$。
• 返回一个大小为 $m$ 的向量，包含 $m$ 个查询的答案。

示例评测程序

示例评测程序读取以下格式的输入：

• 第 $1$ 行：$n$
• 第 $2$ 行：$v[0]\ v[1]\ \ldots\ v[n-1]$
• 第 $3$ 行：$w[0]\ w[1]\ \ldots\ w[n-1]$
• 第 $4$ 行：$m$
• 第 $5+i$ $(0 \leq i \leq m-1)$ 行：$A\ B$

并输出 $m$ 行，调用 solve 的结果。

样例 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)$，有 $2$ 条最优路径：从 $0$ 到 $1$（成本 $1$），$1$ 到 $4$（成本 $1$），$4$ 到 $5$（成本 $1$）；第二条路径是从 $0$ 到 $1$（成本 $1$），$1$ 到 $5$（成本 $2$）。总成本：$1+1+1=1+2=3$。

对于第三个查询 $(0, 6)$，一个成本为 $4$ 的示例路径是从 $0$ 到 $1$（成本 $1$），$1$ 到 $5$（成本 $2$），$5$ 到 $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$ 到 $5$（成本 $1$），$5$ 到 $9$（成本 $2$）$\Longrightarrow$ 总计：$3$
• $(0, 9)$：从 $0$ 到 $1$（成本 $1$），$1$ 到 $5$（成本 $2$），$5$ 到 $9$（成本 $2$）$\Longrightarrow$ 总计：$5$
• $(0, 7)$：从 $0$ 到 $1$（成本 $1$），$1$ 到 $5$（成本 $2$），$5$ 到 $7$（成本 $1$）$\Longrightarrow$ 总计：$4$
• $(0, 4)$：从 $0$ 到 $1$（成本 $1$），$1$ 到 $4$（成本 $2$）$\Longrightarrow$ 总计：$3$
• $(3, 5)$：从 $3$ 到 $5$（成本 $1$）$\Longrightarrow$ 总计：$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$。

详细子任务附加限制及分值如下表所示。