1470. How Many Steps Down the Profile Has

An array of n zeros is given, indexed from 0. Then q updates arrive, each written l r v: add v to every position from l to r - 1. The range is HALF-OPEN, so position r is not changed and an update ending at r and one starting at r change nothing in common.

After all the updates, print how many indices i with 1 <= i <= n - 1 satisfy A[i] < A[i - 1]: how many times the profile steps DOWN as it is read left to right.

n=6, add 2 over [0,3), 3 over [2,5), 1 over [4,6)

The array becomes 2 2 5 3 4 1. Comparing each position with the one before it: 2 to 2 is level, 2 to 5 is up, 5 to 3 is DOWN, 3 to 4 is up, 4 to 1 is DOWN. Two steps down.

n=5, add 1 over [0,5) twice -> 0 the array is flat n=5, add 5 over [0,1), 4 over [1,2), 3 over [2,3), 2 over [3,4) -> 4 5 4 3 2 0 falls throughout

## What most people try first

Building the array and comparing neighbours. That is correct and it needs the array, which needs a difference array and a running total, so it is O(n + q) and it is not slow. It is simply more than the question asks for, and seeing why is the point of the problem.

The naive version, looping over each range, is O(r - l) per update and does reach 10^10 operations at the limits.

## The answer is the difference array, untouched

Build the difference array as usual:

d = array of n + 1 zeros for each update l r v: d[l] += v; d[r] -= v answer = how many i in 1 .. n-1 have d[i] < 0

No running total. No array of values. The loop over d is the whole of the second half.

## Why the difference array IS the profile's steps

The difference array is defined so that the running total through i is A[i]. Subtract the running totals through i and through i - 1 and everything cancels except d[i], so

d[i] = A[i] - A[i - 1] for every i >= 1

A step down at i means A[i] - A[i - 1] < 0, which is d[i] < 0. The difference array was never a scaffold for the answer; it IS the answer, and the running total that usually follows is exactly the step that throws the information away and then has to rebuild it.

Note that d[0] is excluded. It equals A[0] measured against an imaginary zero to the left of the array, and index 0 has no predecessor, so it is not a step at all.

## The boundary that breaks a careless implementation

The range is half-open, so the closing write is d[r] -= v, and r may equal n. That write lands at index n, which is outside the loop 1 .. n-1 and is never read, but the array must be n + 1 long or the write is out of bounds. It is the one write in this problem that affects nothing and still has to happen.

The comparison is strict. A level step, where d[i] is exactly 0, is not a step down, and two updates that touch at r leave d[r] at exactly v_2 - v_1, which can be 0.

## Overflow

10^5 updates of 10^9 on one position reach 10^14, far past the 2147483647 a signed 32 bit integer holds, so the difference entries must be 64 bit. Only their SIGN is read, and a 32 bit entry that wrapped could easily change sign, so this is not a place where a narrow type is harmless. The answer itself is at most n - 1.

## Related

Problem 1464 builds the same difference array and then takes the running total to find the peak. Problem 1466 takes two running totals to answer range sums. This one takes none, which makes it the clearest statement of what a difference array actually holds. Problem 721 does inclusive range increments and prints the array itself.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤ l < r ≤ n`, and the range `[l, r)` is half-open so position `r` is not changed - `-10^9 ≤ v ≤ 10^9` - every position starts at `0`