AcWing 797. 差分
原题链接
简单
作者:
longlongAC
,
2020-06-02 00:47:23
,
所有人可见
,
阅读 633
一点粗陋的见解
#include<bits/stdc++.h>
using namespace std;
const int N =100010;
int n,m,l,r,c;
int a[N],b[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%d",&a[i]); //输入原数组
//构造差分数组 s[i]=s[i-1]+a[i] a[i]=s[i]-s[i-1] 前者叫前缀和数组 后者叫差分数组
for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];
while(m--)
{
scanf("%d%d%d",&l,&r,&c);
b[l]+=c; //差分数组+c b[3]+=c a[2]=b[1]+b[2] 所以a[1~L-1]无影响 只有a[L~末尾]会多加C
//a[l - r] 综合两者 1~l-1 未加C l~末尾会加上C 又因为r+1减了C 所以只有l~r阶段加上了C 例如l=2 r=5 2到结束+c 5到结束-C 最后只有2-5加了C后面部分无影响
b[r+1]-=c;//差分数组-c b[3]-=c a[2]=b[1]+b[2] a[1~r]无影响 a[2+1]=b[1]+b[2]+b[3] 有影响 所以只有a[r+1~结束]这一段减去了C
}
for(int i=1;i<=n;i++) b[i]=b[i-1]+b[i]; //求差分数组的前缀和, 前缀和即为所求数组
for(int i=1;i<=n;i++) printf("%d ",b[i]);
return 0;
}
写的很好,易懂!
###研究了40分钟终于领悟了其中奥秘
写的很到位,y总讲的时候一句话带过了,我那时候也琢磨了半天XD
hhh 我也想了很久 还是要写点实例才能理解