看到好多人都写题解了 (就我没有),手痒写一个,难度不算大,就是公式有点难
题目:
样例:
样例解释:
数据范围:
总体思路
根据数据规模可知:
你要想用暴力那就用,反正浪费时间才搞到70分,你要问我咋么知道的,呵呵呵



不管怎么样,你需要使用差分(两次),然后用一堆公式。。。。
a[pos+1]+=d;
a[pos+len]-=d*len+p;
a[pos+len+1]+=d*(len-1)+p;
a1[pos]+=p;
a1[pos+1]-=p;
额。你想直接拿来用随你,但是后面有解析,(如果老师问你为什么要用这个怎么办,还是接着往下看吧)
核心代码详细解析
a1[pos]+=p;
a1[pos+1]-=p;
a[pos+1]+=d;
a[pos+len]-=d*len+p;
a[pos+len+1]+=d*(len-1)+p;
这个一大堆,我来讲解一下是啥意思
a代表第2层差分
a1代表第1层差分
对于第一次样例操作2, 4, 3, 2,我们可以解析成
a1[pos]+=p;
第一句:p下去,所以a1里pos的位+p。
.
a1[pos+1]-=p;
第二句:保证p不像d一样成为一个倍数递增,a1里只有这一个位置是p,让最终答案数组里他始终+p。
.
a[pos+1]+=d;
第三句:开始对d处理,因为d是在等差数列第二个元素才出现的,所以pos+1位置放d。
.
a[pos+len]-=d*len+p;
第四句:因为目前代码运行的话会出现最后几个数不是0的情况,所以第四句来了,最后几个数永远都是(len - 1) * d + p,所以我们要减去他,但是后来调的时候发现最后几个数虽然没之前那么大了,但还是有,这就是因为a1里还残留着一个d,我们需要减去a1里的这个d,所以是len * d + p。
.
a[pos+len+1]+=d*(len-1)+p;
第五句:呼,终于到最后一句了,因为第四句在a1中残留了一些东西。。。
.
这就能让他=0
最终结论(有点乱,可以跳过):
伪代码
#include<bits/stdc++.h>
using namespace std;
// 最终数组和两个差分数组
int main(){
// 输入n, m;
for(int i=1~m){
// 输入pos, len, p和d
// 刚刚教你们的核心代码
}
for(int i=2~n){
a1[i]+=a1[i-1]+a[i];
}
for(int i=1~n){
s[i]=s[i-1]+a1[i];
// 输出
}
}
OK,最后声明:小编制作不易(午饭都没吃)可以给一个小小的赞么