#O1027. 区间加与单点查询

区间加与单点查询

题目描述

给定长度为 nn 的序列 aa(初始值给定),执行 mm 次操作,每次把区间 [l,r][l, r] 内的所有数加上 xx。所有操作完成后,输出整个序列。

题目类型

差分

输入格式

第一行两个整数 n,mn, m。

第二行 nn 个整数,表示初始序列。

接下来 mm 行,每行三个整数 l,r,xl, r, x。

输出格式

一行 nn 个整数,表示全部操作结束后的序列。

样例 #1

样例输入 #1

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

样例输出 #1

5 4 -1

数据规模与约定

数据范围 说明
1≤n,m≤2×1051 \le n, m \le 2 \times 10^5 长度与操作数
−106≤x≤106-10^6 \le x \le 10^6 增量
−103≤ai≤103-10^3 \le a_i \le 10^3 初值
  • 用差分数组,最后前缀和还原。