给出数组\(a_i\)，表示从点\(i\)可以一次跳到\([i,i+a_i]\)。若干次询问，每次询问区间\([l,r,k]\)，表示区间\([l,r]\)，至多删掉\(k\)个点（\(a_i\)保持不变），从\(l\)跳到\(r\)经过的最少步数。
\(n\le 2*10^4\)
先不考虑删点。考虑跳的策略：每次在能跳到的范围中找到\(i+a_i\)最大的然后跳过去。
考虑了删点时，一次跳跃最多删\(k\)个点，可以视作最多跳到\(i+a_i+k\)。
设\(dp_{j,k,i}\)，表示从\(i\)出发，每次跳\(2^j\)步，删了至多\(k\)个点能跳到的范围（至于为什么不设为能跳到的\(a_i+i\)最大的点，试过就知道它会变得非常奇怪）。
转移：\(dp_{j,k,i}=\max_{t=0}^k dp_{j-1,k-t,([i,dp_{j-1,t,i}]中a_x+x最大的x)}\)。
询问考察对ST表的深刻理解：如果\(k=0\)，按照套路，我们希望通过倍增将能跳到的范围尽量扩展但是不能到达越过\(r\)。现在\(k>0\)，也可以推广一下：设\(g_c\)表示删了\(c\)个点之后能到达的最远距离。每次“尽量扩展”，即尝试扩展一些步数并计算出之后的\(g_c‘\)，如果不存在\(g_c‘\ge r\)则跳，否则不跳。
可以用ST表优化转移。时间\(O(k^2n\lg n)\)（自带三维数组寻址大常数）。
using namespace std;
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define N 20005
#define K 30
#define INF 1000000000
int n,Q;
int a[N];
typedef pair<int,int> info;
int f[15][K+1][N];
info h[15][N];
void inith(){
for (int j=1;1<<j<=n;++j)
for (int i=1;i+(1<<j)-1<=n;++i)
h[j][i]=max(h[j-1][i],h[j-1][i+(1<<j-1)]);
}
int lg[N];
int qryh(int l,int r){
int m=lg[r-l+1];
return max(h[m][l],h[m][r-(1<<m)+1]).se;
}
int g[K+1],d[K+1];
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d%d",&n,&Q);
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
lg[1]=0;
for (int i=2;i<=n;++i)
lg[i]=lg[i>>1]+1;
for (int i=1;i<=n;++i)
h[0][i]=mp(min(i+a[i],n),i);
inith();
for (int k=0;k<=K;++k)
for (int i=1;i<=n;++i)
f[0][k][i]=min(i+a[i]+k,n);
for (int j=1;j<=14;++j)
for (int k=0;k<=K;++k)
for (int i=1;i<=n;++i){
int tmp=i;
for (int t=0;t<=k;++t)
tmp=max(tmp,f[j-1][k-t][qryh(i,f[j-1][t][i])]);
f[j][k][i]=tmp;
}
while (Q--){
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
if (l==r){
printf("0\n");
continue;
}
if (l+a[l]+c>=r){
printf("1\n");
continue;
}
for (int k=0;k<=c;++k)
g[k]=l+a[l]+k;
int ans=0;
for (int j=14;j>=0;--j){
bool bz=0;
for (int k=0;k<=c && !bz;++k){
d[k]=g[k];
for (int t=0;t<=k;++t)
d[k]=max(d[k],f[j][k-t][qryh(l,g[t])]);
bz|=(d[k]>=r);
}
if (bz) continue;
ans+=1<<j;
memcpy(g,d,sizeof(int)*(c+1));
}
printf("%d\n",ans+2);
}
return 0;
}
CF1523H. Hopping Around the Array
原文：https://www.cnblogs.com/jz-597/p/14856283.html