722. Adding a Ramp Across a Range
An array of n zeros is given. Each of q updates is l r v s, meaning: add v at position
l, v + s at l + 1, v + 2s at l + 2, and so on up to v + (r - l) s at position r.
Positions are numbered from 1.
Print the final array.
n = 5, update (1 3 1 1) -> 1 2 3 0 0
n = 4, update (2 4 5 -2) -> 0 5 3 1
n = 2, update (1 2 -5 10) -> -5 5
## A difference array is not enough
Problem 721 works because a CONSTANT range add changes only two of the first differences.
Here the amount added grows, so the first differences change across the WHOLE range: every
position from l + 1 to r now sits s further above its neighbour than before.
In other words, the update is a constant range add applied to the DIFFERENCE array. And a constant range add is exactly what a difference array makes cheap.
So apply the technique twice. That is the whole problem, and it is the moment the technique becomes a tool rather than a trick.
## The second-order array
Let dd be the difference array OF the difference array. The update becomes three impulses:
point add v to d[l] -> dd[l] += v, dd[l+1] -= v
range add s to d[l+1 .. r] -> dd[l+1] += s, dd[r+1] -= s
point add -(v + (r-l)s) to d[r+1] -> dd[r+1] -= last, dd[r+2] += last
Every update is at most six writes, whatever the width.
Recover in two passes: a running total over dd gives d, and a running total over d gives
the answer.
## Why the third impulse is there
After the ramp ends, position r + 1 must fall back to whatever it was before. It sits
v + (r - l) s above position r otherwise, since r was raised by exactly that much and
r + 1 was not. Subtracting it at r + 1 cancels the whole ramp.
Forgetting it leaves the ramp's final height added to every position after the range, which shows on any input where a range stops before the end.
## The guard on the middle impulse
The range add applies to l + 1 .. r, which is empty when l == r. Applying it anyway writes
dd[l+1] += s and dd[r+1] -= s at the SAME index, so the two cancel and no harm is done.
Both spellings are correct here; knowing why is better than picking one by luck.
## Indices up to n + 2
The third impulse writes at r + 2, which reaches n + 2 when r is n. The array must be
that long.
## Overflow
2 * 10^5 positions with s up to 10^4 reach 2 * 10^9 from a single ramp, and q
ramps stack.
## Cost
Time O(n + q). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ q ≤ 200000` - `1 ≤ l ≤ r ≤ n` - `-10^4 ≤ v, s ≤ 10^4`
Input
The first line contains two integers n and q.
Each of the next q lines contains four integers l, r, v and s.
Output
Print the n final values on one line, separated by spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.