1469. Range Adds That Climb as They Go

An array of n zeros is given, indexed from 0. Then q updates arrive, each written l r v e and meaning: add v to position l, v + e to position l + 1, v + 2e to position l + 2, and so on up to position r - 1. The range is HALF-OPEN, so position r gets nothing.

Print the largest value in the finished array and the SMALLEST index holding it.

n=6, add over [0,4) starting 1 step 1, then over [3,6) starting 10 step -3

The first update writes 1, 2, 3, 4 into positions 0 to 3, giving 1 2 3 4 0 0. The second writes 10, 7, 4 into positions 3, 4 and 5, giving 1 2 3 14 7 4. The largest value is 14 at index 3, so the answer is 14 3.

n=5, add over [0,5) starting 1 step 0 -> 1 0 every position gets 1 n=5, add over [0,5) starting 0 step 1 -> 4 4 the values are 0 1 2 3 4

A step of 0 is legal and makes the update an ordinary constant range add. A negative step makes the values fall rather than climb.

Because the range is half-open, two updates that merely TOUCH, one ending at r and the next beginning at r, write to no position in common, and each restarts its ramp from its own v.

## What most people try first

Looping over the range writing v + (i - l) * e at each position. Correct, and O(r - l) per update, so 10^5 updates over the whole array is 10^10 writes.

The second reflex is the difference array from problem 1464. It handles a CONSTANT add in two writes and it does not handle this: adding a climbing sequence changes the step between neighbours at every position inside the range, not at two of them. One difference array is not enough.

## Difference the differences

Let D[i] = A[i] - A[i-1] be the first differences of the finished array. An update l r v e changes D like this:

D[l] += v the jump up at the start D[i] += e for l+1 <= i <= r-1 the constant climb inside D[r] -= v + (r - 1 - l) * e the drop back after the last value

That is a CONSTANT range add on D, plus two point changes. So run a second difference array F over D:

F[l] += v; F[l+1] -= v point add of v at l F[l+1] += e; F[r] -= e constant add of e on [l+1, r) F[r] -= last; F[r+1] += last point subtract at r, where last = v + (r-1-l)*e

Then D is the running total of F, and A is the running total of D. Two nested running totals, O(n + q).

## Why the second difference collapses a climbing add to a constant one

This works because, inside the range, every position is e more than the one before it, so the first difference is the CONSTANT e there. That is always true whatever v is, since v affects only where the ramp starts. A constant over a range is exactly what one difference array handles in two writes. The only irregular places are the two ends: the first value of the range jumps up by v from whatever was before it, and the position just past the range drops by the last value written. Those are two point changes, which a difference array also handles in two writes each.

The same trick extends: a quadratic ramp needs three nested difference arrays, a cubic one four. The degree of the added polynomial is the number of differencing levels.

## The boundary that breaks a careless implementation

last = v + (r - 1 - l) * e, using r - 1 - l and not r - l. The last position written is r - 1, so the multiplier is its offset from l, which is one less than the width. Getting that wrong leaves a residue that corrupts every position after the range.

The write at F[r + 1] means the array needs n + 2 slots, since r can be n.

## Overflow

The largest single value an update can write is 10^5 + 10^5 * 10^5, a little over 10^10, already past the 2147483647 a signed 32 bit integer holds. Stacking 10^5 updates reaches about 10^15, so both running totals need 64 bits. The individual v and e values fit in 32 bits, which is worth noticing rather than widening by reflex.

## Related

Problem 722 adds an arithmetic progression across an INCLUSIVE range and prints the whole array. This one uses half-open ranges, allows a negative or zero step, and asks only for the peak and where it first occurs, so the closing correction lands at r rather than at r + 1 and the multiplier changes with it. Problem 1464 is the constant-add case, which needs only one level of differencing.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ q ≤ 100000` - `0 ≤ l < r ≤ n`, and the range `[l, r)` is half-open so position `r` receives nothing - `-100000 ≤ v ≤ 100000` and `-100000 ≤ e ≤ 100000` - every position starts at `0`