UOJ Logo Universal Online Judge

UOJ

#652. 【APIO2021】雨林跳跃

附件下载 统计

在苏门答腊岛的热带雨林中,有 $N$ 棵树排成一排,从左到右依次用 $0$ 到 $N-1$ 进行编号,其中 $i$ 号树的高度为 $H[i]$,且所有树的高度互不相同。

PakDengklek 正在训练一只猩猩,让她能够从一棵树上跳到另一棵树上。对于一次跳跃,猩猩可以从一棵树,向左或向右跳到比当前这棵树高的第一棵树上。形式化地,如果猩猩当前在 $x$ 号树,那么当且仅当满足下列条件之一时,她能够跳到 $y$ 号树上:

  • $y$ 是满足 $H[z]\gt H[x]$ 的所有 $z$ 中比 $x$ 小的最大非负整数;或者:
  • $y$ 是满足 $H[z]\gt H[x]$ 的所有 $z$ 中比 $x$ 大的最小非负整数。

PakDengklek 有 $Q$ 个跳跃计划,每个计划用四个整数 $A,B,C$ 和 $D(A \le B \lt C \le D)$ 来描述。对于每个计划,PakDengklek 想知道猩猩是否能够从某棵树 $s\ (A \le s \le B)$ 出发,经过若干次跳跃,到达某棵树 $e\ (C \le e \le D)$。若该计划可行,PakDengklek 还想知道可行方案中猩猩需要的最少跳跃次数。

实现细节

你需要实现下列函数:

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$ 次。

例子

考虑如下调用:

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$。

输入格式

示例测试程序按如下格式读取输入数据:

  • 第 $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 调用的返回值。

限制与约定

对于所有数据:

  • $2 \leq N \leq 200\ 000$
  • $1 \leq Q \leq 100\ 000$
  • $1 \leq H[i] \leq N (0 \leq i \leq N-1)$
  • $H[i] \neq H[j] (0 \leq i \lt j \leq N-1)$
  • $0 \leq A \leq B \lt C \leq D \leq N-1$

子任务:

实际测试中,前 16 个 subtask 为数据包,后 7 个 subtask 为 7 个子任务。

  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$ 分) 无附加限制

时间限制:$3\texttt{s}$

空间限制:$1\texttt{GB}$

下载

样例数据下载