程序设计思维与实践 Week5 作业 B - TT's Magic Cat
程序员文章站
2022-07-12 15:17:27
...
解题思路:
利用差分的思想。d[n]=a[n]-a[n-1]。此时如果想对a数组【l,r】区间里的每一个元素都加c。利用公式d[l]+=c; d[r+1]-=c; 先将a数组插入d数组,此时l=r=i。再利用公式对每一个规定区间加c。最后根据sum{d【1…n】}=a[n]输出原数组。注意:d数组需要long long类型。
#include<cstdio>
using namespace std;
const int maxn=1e6;
long long d[maxn];
int n,q;
void insert(int l,int r,int c)
{
d[l]+=c;
d[r+1]-=c;
}
int main()
{
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++)
{
int c;
scanf("%d",&c);
insert(i,i,c);
}
while(q--)
{
int l,r,c;
scanf("%d %d %d",&l,&r,&c);
insert(l,r,c);
}
for(int i=1;i<=n;i++)
{
if(i==1) printf("%lld",d[i]);
else
{
d[i]+=d[i-1];
printf(" %lld",d[i]);
}
}
return 0;
}
上一篇: Springboot集成aop的简单使用
下一篇: [TT's Magic Cat] 差分