题目
输入一个长度为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
分析
1.对数组进行初始化操作: a[1] a[2] a[3] a[4] ...... a[n]
2.对数组进行差分结果是: a[1] a[2] -a[1] a[3] - a[2] a[4] - a[3] ...... a[n] - a[n - 1]
差分性质:
差分性质探索:
3.对数组中[l,r]区间每个数进行添加c: a[1] + c a[2] + c a[3] + c a[4] + c a[5] + c ...... a[n] + c
4.对进行差分操作: a[1] + c a[2] -a [1] ..... a[n] - a[n - 1] a[n + 1] - a[n] -c
Coding
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
int l,r,c;
void insert(int l, int r, int c){
b[l] += c;
b[r + 1] -= c;
}
int main(){
scanf("%d%d",&n, &m);
for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);
for(int i = 1; i <= n; ++i) insert(i, i, a[i]);
while(m--){
scanf("%d%d%d",&l,&r,&c);
insert(l,r,c);
}
for(int i = 1; i <= n; ++i) b[i] += b[i - 1];
for(int i = 1; i <= n; ++i) printf("%d ",b[i]);
return 0;
}