输入一个长度为 n 的整数序列。
接下来输入 m 个操作,每个操作包含三个整数 l,r,c,表示将序列中 [l,r] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数,表示整数序列。
接下来 m 行,每行包含三个整数 l,r,c表示一个操作。
输出格式
共一行,包含 n 个整数,表示最终序列。
数据范围
1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000文章来源:https://www.toymoban.com/news/detail-585322.html
输入样例:
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例:
3 4 5 3 4 2
思路:差分模板套用,对[ L, R] 区间进行增加或减小,都可以转 该数组的差分数组(即前缀和为该位置原本值)的第 L 位置增加或减少 C, 再对 R 位置减少或增加 C, 最后,对该差分数组进行前缀和,即得到修改后的数组值
代码如下:文章来源地址https://www.toymoban.com/news/detail-585322.html
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n, m;
vector<int> nums(N, 0);
vector<int> res(N, 0);
void insert(int l, int r, int c){
res[l] += c;
res[r + 1] -= c;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> nums[i];
}
//求差分数组
for(int i = 1; i <= n; i++){
insert(i, i, nums[i]);
}
while(m--){
int l = 0, r = 0, c = 0;
cin >> l >> r >> c;
insert(l, r, c);
}
for(int i = 1; i <= n; i++){
res[i] += res[i - 1];
cout << res[i] << " ";
}
return 0;
}
到了这里,关于每日打卡day8——差分练习的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!