比较套路的贪心，与之类似的题不少。本篇题解不需要差分。
解法
显然，对这些选定区间的操作顺序不影响答案且没有后效性，所以考虑贪心。
这里选择从后向前贪心。对于位置 $i$，有如图的不超过 $k$ 种区间对 $a_i$ 有影响，且下面的区间对答案的贡献是严格优于上面的区间对答案的贡献的。值得注意的是每种区间可能不止 $1$ 个。
注意到每个区间都是对 $k$ 个位置有影响的，因为我们从后向前贪心，所以对于位置 $i$，对以 $i$ 结尾的长度为 $k$ 的区间需要几个有影响的区间是以 $i + 1$ 结尾到 以 $i + k - 1$ 结尾的长度为 $k$ 的区间。我们统计这些区间的个数和，方法类似于滑动窗口。
统计每种以 $i$ 结尾的长度为 $k$ 的区间有多少个，最后累加即可获得答案。
代码
#include<bits/stdc++.h>
using namespace std;
namespace fast_IO
{
/*
fast Input/Output
*/
};
using namespace fast_IO;
#define int long long
int n,k,a[300010],ans,num[300010],sum,in;
signed main()
{
read(n),read(k);
for(int i=1;i<=n;i++) read(a[i]);
for(int i=n;i-k+1>=1;i--)
{
if(a[i]>sum) num[i]=ceil((a[i]-sum)*1.0/k),sum+=num[i]*k,in+=num[i];
sum-=in;
if(i+k-1<=n) in-=num[i+k-1];
}
for(int i=k-1,delta;i;i--)
{
if(a[i]>sum) delta=ceil((a[i]-sum)*1.0/i),sum+=delta*i,in+=delta,num[k]+=delta;
sum-=in;
if(i+k-1<=n) in-=num[i+k-1];
}
for(int i=1;i<=n;i++) ans+=num[i];
cout<<ans;
return 0;
}
