CF1523H Hopping Around the Array

William 非常想养一只宠物。从小他就梦想拥有一只宠物蚂蚱。William 对选择宠物非常负责，因此他想为蚂蚱设置一个试炼！ 试炼发生在一个长度为 $n$ 的数组 $a$ 上，该数组定义了每个格子的跳跃长度。蚂蚱可以按照以下规则在格子间跳跃：从下标为 $i$ 的格子，它可以跳到下标从 $i$ 到 $i+a_i$（包含两端）之间的任意一个格子。 我们定义某个数组的 $k$-grasshopper 值为：蚂蚱从第一个格子跳到最后一个格子所需的最少跳跃次数，但在开始前你可以选择不超过 $k$ 个格子并将它们从数组中移除。每当移除一个格子时，其他格子的编号会重新排列，但每个格子的 $a_i$ 值保持不变。在此过程中，第一个和最后一个格子不能被移除。 现在需要处理 $q$ 个查询，每个查询格式如下：给定三个数字 $l$、$r$、$k$，你需要求出数组 $a$ 的子数组 $[l, r]$ 的 $k$-grasshopper 值。

第一行包含两个整数 $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)$），分别表示子数组的左右端点和 $k$-grasshopper 值中的 $k$。

对于每个查询，输出一个整数，表示该查询的答案，每行一个。

对于第二个查询，过程如下图所示： 对于第三个查询，过程如下图所示： 由 ChatGPT 4.1 翻译