最详细的题解
题目传送门：Progressions Covering
阅读前人题解时，限于个人能力有限，有一些地方想了好一会儿才懂。发现很多题解都是在 @SDLTF_凌亭风 等作者基础上延伸，但详细程度依旧有限，尽管这篇题解亦是站在他们基础上延伸的，这篇题解更为详细的点明了很多地方。
本人第一次写题解，讲的不是很通顺,如果看不懂您可以对照着其他作者的题解看，见谅。
思路
-
由于数组 \(a\) 刚开始时全是 \(0\)，要通过对 \(a\) 数组一定规则的加法操作使得 \(a\) 数组达到 \(a_i\ge b_i\)，可以转化为仅操作 \(b\) 数组做相同规则的减法，使得 \(b_i\le0\)，如此，我们便不用考虑 \(a\) 数组的问题力。
-
由操作规则可知，对于一个 \(b_i\) 我们取其前面尽可能大的区间，可以使得 \(b_i\) 被减少的最多，可以实现次数更少达到 \(b_i\le0\) 的目的。
因为是取每一个 \(b_i\) 前面的区间，我们贪心的从后往前(从右往左) 扫。 -
由于按照要求我们对一个区间进行等差数列的加减操作，我们很自然可以想到二阶差分的做法，例如：
对于一个区间 \(1-10\) 每个数加 \(10\) 的操作如下（采用一阶差分）：
对于一个区间 \(1-10\) 进行第 \(i\) 个数加 \(i\) 的操作如下（采用二阶差分）：
如果对二阶差分不甚理解，这里有一些经验豆：
P4231 三步必杀
P5026 Lycanthropy
蓝桥杯—绝世武功（此题链接找不到了）
一些具体实现
（这段话比较抽象，可以先看一看程序实现再回来读，如果程序读懂了可以不用再看了。）
- 如何实现差分？
我们用一个 \(tot[i]\) 数组来维护 \(b_i\) 对 \(b_{i-1}\) 至 \(b_{i-k+1}\) 的影响，即为了使 \(b_i\) 减掉 \(k\)，根据操作规则实际上他左边 \(k-1\) 个数也要按规则减去一定值，我们称其为“ \(b_i\) 对左边数的影响”。
具体而言，假设 \(k=5,b_{10}=10\)，为了使 \(b_{10}\) 减到 \(0\)：\(b_{10}\) 要减 \(10\)，相应地 \(b_9\) 要减 \(8\)，\(b_8\) 要减 \(6\)， \(b_7\) 要减 \(4\)，\(b_6\) 要减 \(2\)；此时，要减的 \(2，4，6，8，10\) 构成一个等差数列，如果令 \(tot[6]=2\) 对 \(tot_i\ (i\in[6,10])\) 做前缀和操作，发现数组变为 \(2,2,2,2,2\)。也就是说 \(tot[i]\) 本质上维护了一个二阶差分的角色，使得当前 \(b_i\) 的影响可以顺利向左施加。 - 怎么让之前的影响加在当前数?
利用一个 \(sum\) 维护当前 \(b_i\) 被右侧一面包车数的影响的大小，即如果 \(b_i-sum\le0\) 已经成立，我们对这个数就不用操作了，否则计算要操作的次数并把他对左边接下来的数的影响记录。即 \(sum\) 实现了一阶差分的角色。 - 怎么记录影响？
用一个 \(times\) 记录应该对当前数的操作次数。
用一个 \(newadd\) 记录已经操作次数。
每次更新 \(sum\) 时，要使 \(sum-nowadd\)。
重点: 为什么要减？维护一阶差分。
因为要减的数是一个等差数列，如果对当前数的一个操作减去了 \(x\)，那么这个操作对左边这个数减去的是\(x-1\)，\(nowadd\)记录了目前正在进行 \(nowadd\) 次操作,左边这个数受右边(之前)数的影响应该是 \(sum-nowadd\)，这便巧妙地维护了实际差分的值是等差数列的性质。
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 300030
ll orl[maxn]; //b数组，记录原始的值（original）
ll tot[maxn]; //记录操作次数
int n,k;
ll ans; //答案统计
ll sum; //下一个数应该减去多少？（受到了多少影响）
ll nowadd; //当前进行了多少次操作
inline long long read(){
char readch=getchar(); ll readtmp=0;
ll readflag=1;
while(readch<'0' || '9'<readch){if(readch=='-')readflag=-1;readch=getchar();}
while('0'<=readch && readch<='9'){readtmp=readtmp*10+readch-'0';readch=getchar();}
return readtmp*readflag;
}
int main(){
cin>>n>>k;
for(int i=1; i<=n; i++)
orl[i]=read();
for(int i=n; i>=1; i--){
int pos=max(1,i-k+1); //可以取到的最大区间的左端点（注意细节每一个操作区间左端最小为0）
int jian=i-pos+1; //可以取到的最大区间长度,即当前这个orl[i]一次操作最大减多少
orl[i]-=sum; //之前数对 orl[i]的影响,即之前操作使得orl[i]减去了多少
ll times=0; //还需操作次数
if(orl[i]>0) times=(orl[i]+jian-1)/jian;
if(times>0){
ans+=times;
nowadd+=times;
sum+=1ll*jian*times;
tot[pos]+=times;
}
sum-=nowadd; //重点。
nowadd-=tot[i]; /*重点。减的原因是之前操作过期了,注意一个操作有效期只有操作长度k*/
}
cout<<ans;
return 0;
}