[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 n cities from the world map, and a[i] represents the asset value owned by the i-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 c. And finally, it is required to give the asset value of each city after q 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 a: integer numbers a1,a2,…,an (−106≤ai≤106).
Then q lines follow, each line represents an operation. The i-th line contains three integers l,r and c (1≤l≤r≤n,−105≤c≤105) for the i-th operation.
Output
Print n integers a1,a2,…,an one per line, and ai should be equal to the final asset value of the i-th city.

题目大意

本题给出了一串数字 a[n] 随后给出 q 个询问，对于每个询问给出左右两个边界 l 和 r 还有一个值 c ，要求给[ l , r ] 内的所有值加 c ，最后输出所有询问操作之后 a[n] 的结果。

解题思路

本题如果用暴力求解，则需要的时间复杂度为 O(nq) ，必然会超时，可见直接给对应区间进行加减操作是不可取的。这里使用差分数列就会方便很多。首先对于数列 A ，其差分数列 B 可以表示为：

• B[1] = A[1]
• B[i] = A[i] - A[i-1]

这里可以发现对 A 区间 [ l , r ] 内的元素加 c 不会改变差分数列 B[l+1] ~ B[r] 的值。所以可以将询问中的操作转化为 B[l] += c, B[R+1] -= c 。将所有询问执行结束后，再有差分数列得出原数列的结果就好，即 A[i] = A[i-1] + B[i] 。

具体代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<ctime> 
#include<iomanip>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ld long double
using namespace std;

ll a[200005],b[200005];

int main()
{
	int n,q;
	cin >> n >> q;
	for(int i = 1; i <= n ; i++)
	{
		cin >> a[i];
		if(i == 1)
		{
			b[i] = a[i];
		}
		else
		{
			b[i] = a[i] - a[i-1];
		}
	}
	int l,r,c;
	for(int i = 0; i < q; i++)
	{
		cin >> l >> r >> c;
		b[l] += c;
		b[r+1] -= c;
	}
	for(int i = 1; i <= n; i++)
	{
		if(i == 1)
		{
			a[i] = b[i];
		}
		else
		{
			a[i] = a[i-1] + b[i];
		}
		cout << a[i] << " ";
	}
    return 0;
}