Week5 作业B - TT's Magic Cat [Gym - 272542A]

题目大意

给定一个整数序列，对其进行若干次操作。每次操作选取一个连续的区间，将这个区间中所有的数都加上一个固定的值，要求输出序列中每个数最后是多少。

输入

第一行两个数表示序列长度和操作次数。
第二行给出整数序列。
第三行及之后每行代表一个操作，每行三个数，前两个数代表区间，最后一个数代表要加的值。

输出

在一行中输出序列中每个数最后的值。

样例

基本思路

首先最简单的思路，直接按操作，修改序列里每个数。这样做的确没错，但是效率不高（每次操作时间复杂度$O(n)$O(n)），因为每次操作，加的数是固定的，我们要做若干次重复的操作。

高效的做法是利用前缀和和差分。方便起见，假设原序列有n个数，第i个数为$a_i$ai​(0<=i<n)。

首先我们要维护该序列的差分序列$b$b。$b_i = a_i - a_{i-1}$bi​=ai​−ai−1​(i>=1);$b_0=a_0$b0​=a0​。

可以发现，$b$b的前$i$i项和就是$a_i$ai​。

我们再看需要的操作，我们要对一个连续区间内的数都加上一个固定的值，假设序列为$[m, n)$[m,n)，要加的值为v，那么我们其实只需要给$b_m$bm​加上v，给$b_n$bn​减去v。这样，每次操作复杂度是$O(2)$O(2)。最后，求$b_i$bi​的前缀和即可得到最后的序列a。

注意点

最后序列中的数可能很大，需要使用long long存储。

代码

#include<iostream>
#include<vector>
using namespace std;
int n, opN;
vector<int> v, v1;
int l, r, d;
int main ()
{
	std::ios::sync_with_stdio(false);
	cin>>n>>opN;
	v.resize(n+1);
	v1.resize(n+1);
	for(int i=1;i<=n;i++)	cin>>v[i];
	v1[1] = v[1];
	for(int i=2;i<=n;i++)	v1[i] = v[i] - v[i-1];
	for(int i=0;i<opN;i++)
	{
		cin>>l>>r>>d;
//		if(l > r)	swap(l, r);
//		r = min(n, r);
//		l = max(1, l);
		v1[l] += d;
		if(r < n)	v1[r+1] -= d;
	}
	long long sum=v1[1];
	cout<<sum;
	for(int i=2;i<=n;i++)	cout<<" "<<(sum+=v1[i]);
	return 0;
}