D. 区间加法

内存限制:256 MiB 时间限制:1000 ms 输入文件: add.in 输出文件: add.out
题目类型:传统 评测方式:文本比较

题目描述

假设你有一个长度为 n 的数组 a,初始情况下所有的数字均为 0,你将会被给出 k​​​​​​​ 个更新的操作。

其中,每个操作会用三个数表示:i, j, c,表示将子数组 a[i]a[j] 的每个一个元素增加 c

请你返回 k 次操作后的数组。

输入格式

第一行2个数,nk,表示 数组 an 个元素(初始均为0),有 k 次更新操作

接下来k行,每一行表示一次更新操作,分别用 i, j, c 表示,表示将子数组 a[i]a[j] 的每个一个元素增加 c

输出格式

k 次操作后的数组

样例

输入:

5 3
1 3 2
2 4 3
0 2 -2

输出:

-2 0 3 5 3

解释:

初始状态: [0,0,0,0,0]

进行了操作 [1,3,2] 后的状态: [0,2,2,2,0]

进行了操作 [2,4,3] 后的状态: [0,2,5,5,3]

进行了操作 [0,2,-2] 后的状态: [-2,0,3,5,3]

数据范围与提示

40%数据:1<=n,m<=1000

100%数据:1<=n,m<=200000,1<=i<=j<=n,0<=c<=200000