问题描述：（虽然中计了....）

$给定一个长度为$ n $的序列$ a $。$

$再给定 𝑚 m 组操作$

$每次操作给定3个正整数𝑙,𝑟,𝑑$

$表示对 𝑙 ∼ 𝑟​中的所有数增加 𝑑 。$

$最终输出操作结束后的序列 𝑎 。$

$输入格式 第一行输入两个正整数𝑛,𝑚。$ $（ 1 ≤ 𝑛 , 𝑚 ≤ 2 × 10 5 1≤n,m≤2×10 5 ）$ $第二行输入 𝑛 n 个正整数 𝑎 𝑖 （ 1 ≤ 𝑖 ≤ 𝑛 , 1 ≤ 𝑎 𝑖 ≤ 10 4 ）。$

$接下来 𝑚 m 行，$ $ 每行输入 3 3 个正整数 𝑙 , 𝑟 , 𝑑 l,r,d。

$（ 1 ≤ 𝑙 ≤ 𝑟 ≤ 𝑛 , − 10 4 ≤ 𝑑 ≤ 10 4 1≤l≤r≤n,−10 4 ≤d≤10 4 ）。

第一眼

暴力！！！

#include<bits/stdc++.h>
using namespace std;
void out(){
	cout<<" ";
}
int main(){
	int n,m;
	cin>>n>>m;
	int a[10005];
	for(int i=1;i<=n;i++){
		cin>>a[i];
		while(m--){
			int l,r,d;
			cin>>l>>r>>d;
			for(int j=l;j<=r;j++){
				a[j]+=d;
			} 
		}
	} 
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
	out();
}

Yeah

喜提WA

等一下

标签

差分....

我想

*****************************

回归正题：

差分代码

(复制的是GAY)

code:

#include<bits/stdc++.h>
using namespace std;
void out(){
	cout<<" ";
}
int main(){
	int n,m;
	cin>>n>>m;
	vector<long long> a(n+2,0);
	vector<long long> d(n+2,0);//差分数组
	for(int i=1;i<=n;i++){
		cin>>a[i]; 
	} 
	for(int i=1;i<=m;i++){
		int l,r,dd;
		cin>>l>>r>>dd;
		d[l]+=dd;
		d[r+1]-=dd;
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		cnt+=d[i];
		a[i]+=cnt;
		cout<<a[i]<<" ";
	}
	return 0;
	out();
}

最后，给个视频：