← 返回题目列表

Codeforces · 1523/H

H. 在阵列中跳跃

中文机器翻译题面 查看原题

威廉真的很想养一只宠物。他从小就梦想养一只宠物蚱蜢。威廉对于选择宠物非常负责,所以他想为蚱蜢设立一个试验!

试验在长度为 $$$n$$$ 的数组 $$$a$$$ 上进行,该数组定义每个 $$$n$$$ 单元的跃点长度。蚱蜢可以根据以下规则在销售中跳跃:从索引为 $$$i$$$ 的单元格,它可以跳转到索引从 $$$i$$$ 到 $$$i+a_i$$$(含)的任何单元格。

让我们将某个数组的 $$$k$$$-grasshopper 值称为 Grasshopper 从第一个单元格跳到最后一个单元格所需的最小跳跃数,但在开始之前,您可以选择不超过 $$$k$$$ 单元格并将它们从数组中删除。删除某个单元格后,所有其他单元格都会重新编号,但每个单元格的 $$$a_i$$$ 值保持不变。在此期间,第一个和最后一个单元格可能不会被删除。

需要处理以下格式的 $$$q$$$ 查询:为您提供三个数字 $$$l$$$、$$$r$$$、$$$k$$$。您需要找到数组的 $$$k$$$-grasshopper 值,该数组是数组 $$$a$$$ 的子数组,元素从 $$$l$$$ 到 $$$r$$$(包含在内)。

输入

第一行包含两个整数$$$n$$$和$$$q$$$ ($$$1 \le n, q \le 20000$$$),分别表示数组长度和查询次数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) – 数组的元素。

下面的 $$$q$$$ 行包含查询:每行包含三个整数 $$$l$$$、$$$r$$$ 和 $$$k$$$ ($$$1 \le l \le r \le n$$$, $$$0 \le k \le min(30, r-l)$$$),分别是子数组的边和grasshopper值的个数。

输出

对于每个查询,在新行中打印一个数字 - 对查询的响应。

示例

输入 #1

9 5
1 1 2 1 3 1 2 1 1
1 1 0
2 5 1
5 9 1
2 8 2
1 9 4

输出 #1

0
2
1
2
2

注意

对于第二个查询,过程如下所示:

对于第三个查询,过程如下所示: