思路

首先考虑 $f(s,t)$ 怎么算，发现从 $s$ 开始一直跳到能覆盖它的线段的最右端点即可，正确性显然。

设 $R_i$ 为能覆盖 $i$ 的线段的最右端点，设 $F_s=\sum\limits_{t>s}f(s,t)$，则有 $F_s=n-R_s+F_{R_s+1}$，现在我们解决了没有 $x$ 的问题。

考虑有 $x$ 怎么做，按顺序考虑点 $i$，我们设 $nR=\min(i+x,n)$，它会将某个区间的 $R$ 全部变成 $nR$，显然这个区间两个端点都有单调性，可以简单求出，我们设其为 $[l,r]$，考虑有哪些值发生了改变。

对于 $[l,r]$ 里的点 $p$，先设 $g_p$ 为 $l$ 左边有几个点一直跳 $R_i+1$ 会跳到 $p$，则贡献为 $(n-nR+F_{nR+1}-F_p)\cdot(g_p+1)$，所以我们只需要维护 $g_p$ 和 $F_p\cdot g_p$ 的和，这个是简单的，在移动左端点 $l$ 时将其贡献加到对应的位置上即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
int read(){int p=0,flg=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') flg=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return p*flg;}
int n,x,a[1000010],R[1000010],f[1000010],sum[1000010],F[1000010];
signed main(){
    n=read();x=read();for(int i=1;i<=n;i++) a[i]=read(),R[max(i-a[i],1ll)]=max(R[max(i-a[i],1ll)],min(i+a[i],n));
    for(int i=1;i<=n;i++) R[i]=max(R[i],R[i-1]);for(int i=n;i;i--) f[i]=n-R[i]+f[R[i]+1];for(int i=1;i<=n;i++) F[i]=F[i-1]+f[i];
    int ans=F[n];for(int i=1,l=1,r=0,S=0,FS=0;i<=n;i++){
        int nR=min(i+x,n);for(;r<n&&R[r+1]<nR;r++) S+=sum[r+1],FS+=f[r+1]*sum[r+1];
        for(;l<max(i-x,1ll);l++){
            S-=sum[l];FS-=f[l]*sum[l];
            if(R[l]+1<=r){S+=sum[l]+1;FS+=f[R[l]+1]*(sum[l]+1);}sum[R[l]+1]+=sum[l]+1;
        }int res=F[n];if(l<=r) res+=(r-l+1+S)*(n-nR+f[nR+1])-(F[r]-F[l-1])-FS;ans=min(ans,res);
    }cout<<ans;
    return 0;
}