WEEK 5 B TT's Magic Cat

题目：

Thanks to everyone’s help last week, TT finally got a cute cat. But what TT didn’t expect is that this is a 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]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,q (1≤n,q≤2⋅105) — the number of cities and operations.
The second line contains elements of the sequence aa: integer numbers a1,a2,…,an(−106≤ai≤106)
Then qq lines follow, each line represents an operation. The ii-th line contains three integers l,r and c (1≤l≤r≤n,−105≤c≤105) for the ii-th operation.

output：

Print nn integers a1,a2,…,an one per line, and ai should be equal to the final asset value of the ii-th city.

example：

思路：

假设要处理的数组元素的长度为q，该题如果直接使用对原数组进行处理，则时间复杂度为O(q*n)；如果将原数组转化为差分数组进行处理，则时间复杂度会降为O(q+n)；且如果将原数组转化为差分数组进行处理，将从原来的区间修改转变为点的修改，即A[L,R]会变为B[X]+=C,B[Y+1]-=C，差分数组B的前缀和就是A修改后的最终值。综上，在这选用差分数组进行操作。

代码：

#include <iostream>

using namespace std;

const int N = 1e7;
long long n, k, x, y, c;
long long a[N], b[N], temp[N];

void change()
{
	b[1] = a[1];
	for (long long i = 2; i <= n; i++)
	{
		b[i] = a[i] - a[i - 1];
	}
}

int main()
{
	while (scanf_s("%lld %lld",&n,&k)!=EOF)
	{
		for (long long i = 1; i <= n; i++)
			scanf_s("%lld", &a[i]);
		change();
		for (long long i = 0; i < k; i++)
		{
			scanf_s("%lld %lld %lld", &x, &y, &c);
			b[x] += c;
			b[y + 1] -= c;
		}
		temp[1] = b[1];
		cout << temp[1];
		for (long long i = 2; i <= n; i++)
		{
			temp[i] = temp[i - 1] + b[i];
			cout << ' ' << temp[i];
		}
		cout << endl;
	}
    return 0; 
}