欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

程序设计思维与实践 Week5 作业 B - TT's Magic Cat

程序员文章站 2022-07-12 15:17:27
...

程序设计思维与实践 Week5 作业 B - TT's Magic Cat程序设计思维与实践 Week5 作业 B - TT's Magic Cat解题思路:
利用差分的思想。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;
}