AcWing 797. 差分
原题链接
简单
作者:
月下邂逅
,
2024-04-21 13:59:29
,
所有人可见
,
阅读 1
C++ 代码
#include<iostream>
using namespace std;
const int N=1000010;
int a[N],s[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s[i]=a[i]-a[i-1];//令s[i]=a[i]-a[i-1],s为差分矩阵,求a[i]只需要a[i]=s[i]+a[i-1]即可
}
int l,r,c;
while(m--)
{
scanf("%d%d%d",&l,&r,&c);//由公式可知a[i]若要加上c只需要s[i]或a[i-1]加上c即可
s[l]+=c;//左端s[l]加上c可以使a[l]加c,且a[l]在加上c后右侧每一次a[i]=s[i]+a[i-1]都能多一个c
s[r+1]-=c;//因为a[r]已经加上了c,所以要使r后的数据不加c,需要将s[r-1]减去c
}
for(int i=1;i<=n;i++)
{
a[i]=s[i]+a[i-1];
printf("%d ",a[i]);
}
return 0;
}