蓝桥杯·算法提高 VIP 分苹果

时间限制: 1Sec 内存限制: 128MB 提交: 1996 解决: 568

题目描述
一群儿童依次排列，教师向他们分发苹果。
儿童从左至右依次编号为1…N。共有M位教师，每位教师会向从Li到Ri的区间内的所有儿童每人发放Ci个苹果。
最终教师希望了解每位儿童所获得的苹果数量。

数据规模和约定
对于全部测试用例，N、M≤100 000，且满足1≤Li≤Ri≤N，0≤Ci≤100。

输入
第一行包含两个整数N、M，分别表示儿童的数量与教师的数量。
随后M行，每行给出三个整数Li、Ri、Ci，其含义与题意一致。

输出
输出一行包含N个数字，其中第i个数字代表第i位儿童所持有的水果数量。

样例输入
5 3
1 2 1
2 3 2
2 5 3
样例输出
1 6 5 3 3

思路：由于数据规模较大，采用普通的双重循环结构必然会导致运行超时问题。通过分析可知，在分发苹果的过程中，每个区间内的操作均具有连续性特征。因此可以考虑引入差分数组这一方法进行处理。

接下来简要说明差分数组的概念。

差分数组本质上是一种特殊的数组结构。其核心思想是计算原始数组中相邻元素之间的差值，并将其存储于新的数组中。具体而言，令d[i] = a[i+1] - a[i]。通过一次遍历即可完成该差分数组的构建过程。

以下展示了一个典型的差分数组示例