首先考虑 \(k = 0\) 的情况。
贪心，最后一步之前每个 \(i\) 只会跳到 \(j \in [i, i + a_i]\) 且 \(j + a_j\) 最大的点 \(j\)，这个信息或许可以线性处理？但是我没脑子，我用线段树维护，时间复杂度 \(\mathcal O(n \log n)\)。
然后就可以倍增了，时间复杂度 \(\mathcal O(n \log n)\)。
加入 \(k \ne 0\) 的情况，设 \(f(i, j, k)\) 表示从 \(i\) 出发跳 \(2^j\) 步，删了 \(k\) 个点的最远可达位置。
同时又注意到删点其实相当于扩大可达范围，也就是在跳一步的情况下，删 \(k\) 个点后可达范围从 \([i, i + a_i]\) 变成了 \([i, i + a_i + k]\)。
于是就很好转移了，时间允许枚举每个状态的 \(k\) 暴力做转移，时间复杂度 \(\mathcal O(nk^2 \log n)\)。
倍增的一大特色是统计答案和状态转移特像，也是直接暴力做就好。
- 若 \(l = r\)，则答案为 \(0\)。
- 若 \(r \in [l, l + a_l + k]\)，则答案为 \(1\)。
- 否则开始倍增，第 \(2^j\) 步能跳当且仅当无论如何都不会使最大可达范围覆盖到 \(r\)，答案即为步数 \(+ 2\)。
时间复杂度 \(\mathcal O(nk^2 \log n)\)。
总时间复杂度就是 \(\mathcal O[(n + q)k^2 \log n]\)。
代码：
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e4 + 10, LN = 15, K = 31;
int n, q, a[N];
struct Node {
int w, id;
Node() {}
Node(int i) : w(a[i] + i), id(i) {}
Node(int w, int id) : w(w), id(id) {}
Node operator+(const Node &rhs) const {return w < rhs.w ? rhs : *this;}
} f[N][LN][K];
namespace SGT {
#define lson pos << 1
#define rson pos << 1 | 1
Node t[N << 2];
void build(int pos, int l, int r) {
if (l == r) {t[pos] = {a[l] + l, l}; return;}
int mid = (l + r) >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
t[pos] = t[lson] + t[rson];
}
Node query(int pos, int l, int r, int x, int y) {
if (x <= l && r <= y) {return t[pos];}
int mid = (l + r) >> 1;
if (y <= mid) return query(lson, l, mid, x, y);
if (x > mid) return query(rson, mid + 1, r, x, y);
return query(lson, l, mid, x, y) + query(rson, mid + 1, r, x, y);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> q; for (int i = 1; i <= n; i++) cin >> a[i];
SGT::build(1, 1, n);
for (int i = 1; i <= n; i++) {
f[i][0][0] = SGT::query(1, 1, n, i, i + a[i]);
for (int k = 1; k <= 30; k++) f[i][0][k] = Node(f[i][0][k - 1].w + 1, f[i][0][k - 1].id) + Node(a[i] + i + k);
for (int k = 0; k <= 30; k++) f[i][0][k].w = min(f[i][0][k].w, n), f[i][0][k].id = min(f[i][0][k].id, n);
}
for (int j = 1; j < LN; j++) {
for (int i = 1; i <= n; i++) {
for (int k = 0; k <= 30; k++) {
for (int k1 = 0; k1 <= k; k1++) {
f[i][j][k] = f[i][j][k] + f[f[i][j - 1][k1].id][j - 1][k - k1];
}
}
}
}
int l, r, lim, cur[K];
while (q--) {
cin >> l >> r >> lim;
if (l == r) {cout << "0\n"; continue;}
if (l + a[l] + lim >= r) {cout << "1\n"; continue;}
fill(cur, cur + lim + 1, l); int ans = 2;
for (int j = LN - 1; j >= 0; j--) {
bool trans = 1;
for (int k = 0; k <= lim; k++) if (f[cur[k]][j][lim - k].w >= r) {trans = 0; break;}
if (!trans) continue;
ans += (1 << j);
for (int k = lim; k >= 0; k--) {
Node mx = {0, 0};
for (int k1 = 0; k1 <= k; k1++) mx = mx + f[cur[k1]][j][k - k1];
cur[k] = mx.id;
}
}
cout << ans << '\n';
}
return 0;
}