区间加

课程自编 · 一维差分

题目描述

有一个长度为 $n$ 的数组，初始时所有元素都是 $0$。执行 $m$ 次操作，每次操作给出 $l,r,c$，表示把区间 $[l,r]$ 内的所有元素都加上 $c$。输出全部操作结束后的数组。

输入格式

第一行两个整数 $n,m$。接下来 $m$ 行，每行三个整数 $l,r,c$。

输出格式

输出一行 $n$ 个整数，相邻两个整数之间用一个空格分隔，表示最终的数组。

数据范围与约定

$1 \le n,m \le 2\times 10^5$，$1 \le l \le r \le n$，$|c| \le 10^9$。

样例输入

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

样例输出

2 5 5 3 -1

样例说明

第一次操作后为 $2,2,2,0,0$；第二次后为 $2,5,5,3,0$；第三次后为 $2,5,5,3,-1$。用差分数组只需在 $l$ 加 $c$、在 $r+1$ 减 $c$，最后做一次前缀和。

说明

课程自编题，数据由 src/gen.py 生成。