Description

在一个平行宇宙中，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$ 层，他最少需要牺牲多少滴血？

Input Format

你需要实现以下函数：

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

• 接收数组 $v$（表示从每层出发的楼梯最大可上升的层数）和 $w$（表示从每层出发的通风口最大可上升的层数），它们的长度均为 $n$。
• 还接收 $m$ 个询问 queries，一个大小为 $m$ 的数组，每个元素是一个二元组 $(A, B)$，含义如上所述。
• 返回一个长度为 $m$ 的数组，包含每个询问的最少血滴消耗。

7
2 3 1 1 1 1 2
3 4 1 2 1 2 2
3
0 4
0 5
0 6

2
3
4

10
1 1 1 2 3 2 1 1 2 3 
2 4 1 4 1 4 1 3 2 3 
5
3 9
0 9
0 7
0 4
3 5

3
5
4
3
1

Hint

样例解释 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 完成