A18830. 基础区间修改
填空题
较难
知识点
题目描述
基础区间修改
题目描述
给定一个长度为 n 的初始全0数组，进行 m 次操作，每次操作给出 l, r, k，表示将区间 [l, r] 的所有元素加上 k。所有操作结束后，输出最终的数组。
输入格式
第一行两个整数 n, m（1≤n,m≤100000）
接下来 m 行，每行三个整数 l, r, k（1≤l≤r≤n，-1000≤k≤1000）
输出格式
一行n 个整数，表示修改后的数组，元素之间用空格分隔
样例输入
5 2
1 3 2
2 4 -1样例输出
2 1 1 -1 0参考答案
#include <iostream>
#include <vector>
using namespace std;
const int N = 100010;
long long d[N]; // 差分数组，开long long防溢出
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); // 快读优化，适配大数据
int n, m;
cin >> n >> m;
while(m--)
{
int l, r, k;
cin >> l >> r >> k;
d[l] += k;
d[r+1] -= k;
}
// 前缀和还原数组
long long res = 0;
for(int i = 1; i <= n; i++)
{
res += d[i];
cout << res << " ";
}
return 0;
}
上一题
下一题