Logo Universal Online Judge

UOJ

时间限制:3 s 空间限制:1024 MB

#2056. jump

统计

题目描述

给出一个 $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.inex_jump2.out,该测试用例满足子任务 1 的约束 条件。

样例 3

见下发文件 ex_jump3.inex_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.inex_jump5.out,该测试用例满足子任务 2 的约束 条件。

样例 6

见下发文件 ex_jump6.inex_jump6.out,该测试用例满足子任务 3 的约束 条件。

样例 7

见下发文件 ex_jump7.inex_jump7.out,该测试用例满足子任务 3 的约束 条件。

样例 8

见下发文件 ex_jump8.inex_jump8.out

样例 9

见下发文件 ex_jump9.inex_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$

下发样例