33OJ
登录 注册

#S0006. 小 z 的跳跃游戏

小 z 的跳跃游戏

题目描述

有 nn 个格子排成一排,编号为 1,2,…,n1,2,\dots,n。第 ii 个格子有一个跳跃力 aia_i。从格子 ii 出发,可以跳到区间

[i+1, min⁡(n, i+ai)][i+1,\ \min(n,\ i+a_i)]

中的任意一个格子。

有 qq 次询问,每次给出起点 ss 和终点 tt,满足 s<ts<t。求从 ss 跳到 tt 最少需要跳几次。保证对于每次询问,从 ss 一定可以到达 tt。

输入格式

第一行两个整数 n,qn,q。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n。

接下来 qq 行,每行两个整数 s,ts,t,表示一次询问。

输出格式

输出 qq 行,每行一个整数,表示对应询问的最少跳跃次数。

5 3
2 3 1 1 1
1 5
1 4
2 5
2
2
1

样例解释

  • 询问 1→51\to 5:可以 1→2→51\to 2\to 5,共 22 步。
  • 询问 1→41\to 4:可以 1→2→41\to 2\to 4,共 22 步。
  • 询问 2→52\to 5:因为 2+a2=52+a_2=5,可以直接 2→52\to 5,共 11 步。

数据范围

对于 100%100\% 的数据:

1≤n,q≤2×105,n>11\le n,q\le 2\times 10^5,n>1 1≤ai≤n1\le a_i\le n 1≤s<t≤n1\le s<t\le n

保证每次询问从 ss 一定能到达 tt。