B - TT's Magic Cat（差分）

B - TT’s Magic Cat

• 题意：
  One day, the magic cat decided to investigate TT’s ability by giving a problem to him. That is select nn cities from the world map, and a[i]a[i] represents the asset value owned by the ii-th city.
  Then the magic cat will perform several operations. Each turn is to choose the city in the interval [l,r][l,r] and increase their asset value by cc. And finally, it is required to give the asset value of each city after qq operations.
  Could you help TT find the answer?

• 输入输出：
  Input
  The first line contains two integers n,qn,q (1≤n,q≤2⋅105)(1≤n,q≤2·105) — the number of cities and operations.
  The second line contains elements of the sequence aa: integer numbers a1,a2,…,ana1,a2,…,an (−106≤ai≤106)(−106≤ai≤106).
  Then qq lines follow, each line represents an operation. The ii-th line contains three integers l,rl,r and cc (1≤l≤r≤n,−105≤c≤105)(1≤l≤r≤n,−105≤c≤105) for the ii-th operation.
  Output
  Print nn integers a1,a2,…,ana1,a2,…,an one per line, and aiai should be equal to the final asset value of the ii-th city.
  

• 解题思路：
  差分数组：记录与前一个数的差值，好处是在一个范围内的所有值都需要加上或减去同一个数时，只需要修改范围端点的两个值，大大降低复杂度。 显然，本题适用。
  定义long long型差分数组a，将差值存入，因为数组从零开始，l,r为修改范围，每次给数组中l-1和r位置的值加上c，最后将数字加上差值得到原数字输出即可。

• 代码实现：

#include <iostream>
using namespace std;

long long a[1000010]; 
int main()
{
	int n,m,s1=0,s2;
	cin>>n>>m;
	for (int i = 0;i < n;i++)
	{
		cin>>s2;
		s1=s2-s1;
		a[i]=s1;
		s1=s2;
	}
	int l,r,c;
	while (m--)
	{
		cin>>l>>r>>c;
		a[l-1]+=c;
		a[r]-=c;
	}
	cout<<a[0]<<" ";
	for (int i=1;i<n-1;i++)
	{
		cout<<a[i]+a[i-1]<<" ";
		a[i]=a[i]+a[i-1];
	}
	if(n>1)
		cout<<a[n-1]+a[n-2]<<endl;
}