Stacked Range Additions

Difficulty: 1400 3500 ms 128 MB

prefix-sums

Starting from an all-zero array of length N, apply M updates 'add V to every element in [L, R]'. Print the final array.

Input: the first line has N and M; each of the next M lines has L R V.

Output: the final N values.

Constraints:

• 1 ≤ N, M ≤ 10⁵
• |V| ≤ 100

Sample Tests

5 2
1 3 2
2 5 1

2 3 3 1 1

1 1
1 1 -5

-5

Read the Editorial