[APIO2021] 雨林跳跃
题目背景
本题只支持 C++ 提交,不支持 C++14 (GCC 9),提交时不需要包含 jumps.h 头文件,只需要将附件中的 jumps.h 中的内容粘贴到代码的开头即可。
由于洛谷的测试点限制,本题只能评测其中的 100 组数据。
题目描述
在苏门答腊岛的热带雨林中,有 $N$ 棵树排成一排,从左到右依次用 $0$ 到 $N-1$ 进行编号,其中 $i$ 号树的高度为 $H[i]$,且所有树的高度**互不相同**。
Pak Dengklek 正在训练一只猩猩,让她能够从一棵树上跳到另一棵树上。对于一次跳跃,猩猩可以从一棵树,向左或向右跳到比当前这棵树高的第一棵树上。形式化地,如果猩猩当前在 $x$ 号树,那么当且仅当满足下列条件之一时,她能够跳到 $y$ 号树上:
- $y$ 是满足 $H[z]>H[x]$ 的所有 $z$ 中比 $x$ 小的最大非负整数;或者:
- $y$ 是满足 $H[z]>H[x]$ 的所有 $z$ 中比 $x$ 大的最小非负整数。
Pak Dengklek 有 $Q$ 个跳跃计划,每个计划用四个整数 $A$,$B$,$C$ 和 $D$($A \le B<C \le D$)来描述。对于每个计划,Pak Dengklek 想知道猩猩是否能够从某棵树 $s$($A \le s \le B$)出发,经过若干次跳跃,到达某棵树 $e$($C \le e \le D$)。若该计划可行,Pak Dengklek 还想知道可行方案中猩猩需要的最少跳跃次数。
你需要实现下列函数:
`void init(int N, int[] H)`
- $N$:树的数量。
- $H$:大小为 $N$ 的数组,$H[i]$ 表示 $i$ 号树的高度。
- 该函数在第一次 `minimum_jumps` 的调用前,将会被调用恰好一次。
`int minimum_jumps(int A, int B, int C, int D)`
- $A,B$:可以用作起点的树的编号范围。
- $C,D$:可以用作终点的树的编号范围。
- 该函数需要返回可行方案中猩猩需要的最少跳跃次数,或者返回 $-1$ 表示该计划不可行。
- 该函数将被调用恰好 $Q$ 次。
输入输出格式
输入格式
示例测试程序按如下格式读取输入数据:
- 第 $1$ 行:$N$ $Q$
- 第 $2$ 行:$H[0]$ $H[1]$ $\cdots$ $H[N-1]$
- 第 $3+i$($0 \le i \le Q-1$)行:$A$ $B$ $C$ $D$,表示第 $i$ 次 `minimum_jumps` 调用的参数。
输出格式
示例测试程序按如下格式输出你的答案:
- 第 $1+i$($0 \le i \le Q-1$)行:第 $i$ 次 `minimum_jumps` 调用的返回值。
输入输出样例
输入样例 #1
7 3
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2
输出样例 #1
2
1
-1
说明
**【样例解释】**
考虑如下调用:
`init(7, [3, 2, 1, 6, 4, 5, 7])`
在初始化完成后,考虑如下调用:
`minimum_jumps(4, 4, 6, 6)`
该计划意味着猩猩必须从 $4$ 号树(高度为 $4$)出发,并到达 $6$ 号树(高度为 $7$)。
一种跳跃次数最少的可行方案为:先跳到 $3$ 号树(高度为 $6$),再跳到 $6$ 号树。
另一种方案为:先跳到 $5$ 号树(高度为 $5$),再跳到 $6$ 号树。
因此,`minimum_jumps` 应该返回 $2$。
考虑另一个调用:
`minimum_jumps(1, 3, 5, 6)`
该计划意味着猩猩必须从 $1$ 号树(高度为 $2$),$2$ 号树(高度为 $1$),或 $3$ 号树(高度为 $6$)之一出发,并最终到达 $5$ 号树(高度为 $5$)或者 $6$ 号树(高度为 $7$)。
唯一一种跳跃次数最少的可行方案为:从 $3$ 号树出发,直接跳到 $6$ 号树。
因此,`minimum_jumps` 应该返回 $1$。
考虑另一个调用:
`minimum jumps(0, 1, 2, 2)`
该计划意味着猩猩必须从 $0$ 号树(高度为 $3$)或者 $1$ 号树(高度为 $2$)出发,并最终到达 $2$ 号树(高度为 $1$)。
由于 $2$ 号树是高度最低的树,所以无法从其他树上跳到 $2$ 号树。
因此,`minimum_jumps` 应该返回 $-1$。
**【数据范围】**
- $2 \le N \le 2 \times {10}^5$。
- $1 \le Q \le {10}^5$。
- $1 \le H[i] \le N$($0 \le i \le N - 1$)。
- $H[i]\ne H[j]$($0 \le i<j \le N - 1$)。
- $0 \le A \le B<C \le D \le N - 1$。
**【子任务】**
1. (4 分):$H[i]=i+1$($0 \le i \le N-1$)。
2. (8 分):$N,Q \le 200$。
3. (13 分):$N,Q \le 2000$。
4. (12 分):$Q \le 5$。
5. (23 分):$A=B$,$C=D$。
6. (21 分):$C=D$。
7. (19 分):无附加限制。