题目描述
给出一个 $1,\dots,n+1$ 的排列 $v_{1,\dots,n+1}$,与两组权值 $a_{1,\dots,n}$、$b_{1,\dots,n}$。满足 $v_{n+1}=n+1$。
构造一张 $n+1$ 个点的 有向图:
- 对于 $i=1,\dots,n$,从 $i$ 向 $i+1$ 连一条权值为 $a_i$ 的边;
- 对于 $i=1,\dots,n$,找到最小的 $i < j \le n+1$ 满足 $v_j>v_i$,从 $i$ 向 $j$ 连一条权值为 $b_i$ 的边。
一条路径的权值为路径上边权的 最大值。特别地,若一条路径不包含任何边,则其权值为 $0$。
有 $q$ 次询问,每次询问给出 $x,y$($x \le y$),求 $x$ 到 $y$ 的权值最小的路径的权值。
输入格式
输入的第一行包含三个数 $n,q,S$。其中 $S$ 表示测试点所属的子任务编号。第二行包含 $n$ 个数,表示 $v_{1,\dots,n}$。第三行包含 $n$ 个数,表示 $a_{1 ,\dots,n}$。第四行包含 $n$ 个数,表示 $b_{1,\dots,n}$。 接下来 $q$ 行,其中第 $i$ 行包含两个数 $x,y$,表示第 $i$ 次询问。
输出格式
输出应包含 $q$ 行,第 $i$ 行包含一个数,表示你对第 $i$ 个询问求出的答案。
样例数据
样例 1 输入
6 6 4
4 1 6 3 5 2
2 3 2 6 5 3
5 5 4 1 2 5
5 7
1 3
1 7
2 6
6 7
3 3
样例 1 输出
2
3
3
5
3
0
样例 2
见下发文件 ex_jump2.in
和 ex_jump2.out
,该测试用例满足子任务 1 的约束
条件。
样例 3
见下发文件 ex_jump3.in
和 ex_jump3.out
,该测试用例满足子任务 1 的约束
条件。
样例 4 输入
8 10 2
8 7 6 5 4 3 2 1
5 2 3 5 9 4 3 8
7 3 4 4 1 2 8 3
1 3
6 8
7 9
9 9
1 9
1 8
4 4
2 9
2 6
1 3
样例 4 输出
5
4
3
0
5
9
0
3
9
5
样例 5
见下发文件 ex_jump5.in
和 ex_jump5.out
,该测试用例满足子任务 2 的约束
条件。
样例 6
见下发文件 ex_jump6.in
和 ex_jump6.out
,该测试用例满足子任务 3 的约束
条件。
样例 7
见下发文件 ex_jump7.in
和 ex_jump7.out
,该测试用例满足子任务 3 的约束
条件。
样例 8
见下发文件 ex_jump8.in
和 ex_jump8.out
。
样例 9
见下发文件 ex_jump9.in
和 ex_jump9.out
。
数据规模与约定
全部数据均保证 $1 \le n,q \le 5 \times 10^5$,$1 \le a_i,b_i \le 10^9$,$1 \le x \le y \le n+1$。
本题采用子任务捆绑测试,各个子任务详细信息如下:
编号 | 子任务分数 | $n,q \le$ | 特殊性质 |
---|---|---|---|
1 | $20$ | $2000$ | |
2 | $10$ | $5 \times 10^5$ | 对于所有 $i \in [1,n]$,满足 $v_i=n-i+1$ |
3 | $20$ | $10^5$ | $v_i$ 在所有可能的 $n!$ 种排列中均匀随机生成 |
4 | $50$ | $5 \times 10^5$ |