B - TT's Magic Cat（Week5 作业）

题目

Examples

Input

4 2
-3 6 8 4
4 4 -2
3 3 1

Output

-3 6 9 2

Input

2 1
5 -2
1 2 4

Output

9 2

Input

1 2
0
1 1 -8
1 1 -6

Output

-14

题目思路

本题是一道经典的差分题目
	·B[1] = A[1]
	`B[i] = A[i+1]-A[i]
	（B 数组前缀和 = A 数组元素值）
将对数组A的操作转换为对数组B的操作；
将对数组A区间的修改转换为数组B的单点操作。
从而快速实现对数组A区间的变换。

经测试，如果不使用差分，用cin只能过4个测试点，用scanf只能过6个测试点。

实现细节

注意数据范围，使用整型int 会超范围导致wrong answer

代码实现

#include<iostream>
using namespace std;
int n,q;
long long a[300010],b[300010];
int main()
{
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	b[1]=a[1]; 
	for(int j=2;j<=n;j++)
		b[j]=a[j]-a[j-1];
	for(int i=0;i<q;i++)
	{
		int l,r,c;
		scanf("%d %d %d",&l,&r,&c);
		b[l]+=c;
		b[r+1]-=c;
	}
	long long temp=0;
	for(int i=1;i<=n;i++)
	{
		temp+=b[i];
		printf("%lld ",temp);
	}
	return 0;	
}