Range Updates With a Difference Array
easyArrays & Prefix Sums+10 XPTime limit 2s
A row of n lamps all start with brightness 0. You receive q instructions "add x to the brightness of every lamp from l to r" (x may be negative). After all instructions, print the brightness of every lamp.
Input:
- line 1:
n q - next
qlines:l r x(1-based,l ≤ r)
Output: one line with the n final brightness values.
Constraints: 1 ≤ n, q ≤ 10⁵, −10⁴ ≤ x ≤ 10⁴.
Think about it: updating every lamp in the range costs O(n) per instruction. Instead keep a difference array: add x at l and subtract x just after r. One prefix sum at the end turns the differences into the final values — O(n + q) in total.
Sample input 1
5 3 1 3 2 2 5 -1 4 4 10
Sample output 1
2 1 1 9 -1
Sample input 2
1 1 1 1 7
Sample output 2
7
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).