和 std 的复杂度一样但是跑得很慢，不清楚原因。

随机的满数据本机约跑 3.6s /ll

https://codeforces.com/contest/1523/submission/143053079

#include<bits/stdc++.h>
using namespace std;
const int maxn=40010,maxN=15,maxk=31;
int i,j,k,h,n,m,a[maxn],dp[maxN][maxn][maxk],f[maxn][maxk][maxN],ans[maxk],tmp[maxk],tmpf[maxn][maxk][maxN];
int Log[maxn];
struct query{
    int L,R,k,to[maxk],ans;
}Q[maxn];
int find(int L,int R,int k){
    int len=R-L+1,L2=Log[len];
    return max(f[L][k][L2],f[R-(1<<L2)+1][k][L2]);
}
int main(){
    freopen("H.in","r",stdin);
    freopen("H.out","w",stdout);
    Log[0]=-1;for(i=1;i<maxn;i++)Log[i]=Log[i/2]+1;
    cin>>n>>m;
    for(i=1;i<=n;i++)scanf("%d",&a[i]);
    for(i=1;i<=n;i++)for(j=0;j<maxN;j++)for(k=0;k<maxk;k++)dp[j][i][k]=min(n,i+a[i]+k);
    for(i=1;i<=m;i++)scanf("%d%d%d",&Q[i].L,&Q[i].R,&Q[i].k),Q[i].to[0]=Q[i].L;
    for(j=0;j<maxN;j++){
        for(i=n;i>=1;i--){
            if(j){
                for(k=0;k<maxk;k++)
                    for(h=0;h+k<maxk;h++)
                        dp[j][i][k+h]=max(dp[j][i][k+h],find(i+1,dp[j-1][i][k],h));
                for(k=1;k<maxk;k++)
                    dp[j][i][k]=min(n,max(dp[j][i][k],dp[j][i][k-1]+1));
            }
        }
        for(i=n;i>=1;i--)
            for(k=0;k<maxk;k++){
                f[i][k][0]=dp[j][i][k];
                for(h=1;h<maxN && i+(1<<h-1)<=n;h++)f[i][k][h]=max(f[i][k][h-1],f[i+(1<<h-1)][k][h-1]);
            }
    }
	cerr << (1.0*clock()/CLOCKS_PER_SEC) << endl;
    for(j=maxN-1;j>=0;j--){
        for(i=n;i>=1;i--){
            for(k=0;k<maxk;k++)
                f[i][k][0]=dp[j][i][k];
            for(k=0;k<maxk;k++)
                for(h=1;h<maxN && i+(1<<h-1)<=n;h++)
                    f[i][k][h]=max(f[i][k][h-1],f[i+(1<<h-1)][k][h-1]);
        }
        for(i=1;i<=m;i++){
            memset(tmp,0,sizeof(tmp));
            for(k=0;k<=Q[i].k;k++)
                for(h=0;k+h<=Q[i].k;h++){
                    //if(j==0 && i==5)cerr<<"find "<<Q[i].L<<' '<<Q[i].to[k]<<' '<<h<<' '<<' '<<find(Q[i].L,Q[i].to[k],h)<<endl;
                    if(Q[i].to[k])tmp[k+h]=max(tmp[k+h],find(Q[i].L,Q[i].to[k],h));
                }
            bool b=true;
            for(k=0;k<=Q[i].k;k++)
                if(tmp[k]>=Q[i].R){b=false;break;}
            if(!b)continue;
            Q[i].ans+=(1<<j);
            for(k=0;k<=Q[i].k;k++)
                Q[i].to[k]=tmp[k];
        }
    }
    for(i=1;i<=m;i++)printf("%d\n",(Q[i].L==Q[i].R?0:Q[i].ans+1));
	cerr << (1.0*clock()/CLOCKS_PER_SEC) << endl;
}
/*
28 1
4 5 5 4 4 5 5 4 1 2 3 1 3 5 4 4 5 3 6 5 5 1 4 4 1 5 5 4
1 28 0
*/