传统题 2000ms 256MiB

区间加

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

区间加

课程自编 · 一维差分

题目描述

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

输入格式

第一行两个整数 n,mn,m。接下来 mm 行,每行三个整数 l,r,cl,r,c。

输出格式

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

数据范围与约定

1≤n,m≤2×1051 \le n,m \le 2\times 10^5,1≤l≤r≤n1 \le l \le r \le n,∣c∣≤109|c| \le 10^9。

样例输入

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

样例输出

2 5 5 3 -1

样例说明

第一次操作后为 2,2,2,0,02,2,2,0,0;第二次后为 2,5,5,3,02,5,5,3,0;第三次后为 2,5,5,3,−12,5,5,3,-1。用差分数组只需在 ll 加 cc、在 r+1r+1 减 cc,最后做一次前缀和。

说明

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

HGNU ACM Training Round #19

未参加
状态
已结束
规则
XCPC
题目
8
开始于
2026-11-16 19:00
结束于
2026-11-16 21:00
持续时间
2 小时
主持人
参赛人数
15