465. Runs With a Bounded Maximum
Given L and R, count the CONTIGUOUS non-empty runs whose largest element lies in
[L, R] inclusive.
2 1 4 3, L = 2, R = 3 -> 3 the runs [2], [2 1], [3]
2 9 2 5 6, L = 2, R = 8 -> 7
Checking every run is O(n^2) and can be made to pass at small n, but the intended
solution is linear and rests on one substitution.
Counting runs whose maximum is in a RANGE is awkward, because the condition involves
two bounds at once. Counting runs whose maximum is at most X is easy, because it is
equivalent to a much simpler statement: EVERY element of the run is at most X.
So define atMost(X) as the number of runs with every element at most X, and:
answer = atMost(R) - atMost(L - 1)
Every run counted by atMost(R) but not by atMost(L-1) has a maximum at most R
and greater than L-1, which is exactly the range wanted.
atMost(X) is a single scan. Walk the array tracking the length of the current
stretch of elements at most X, adding that length at each step, and resetting to 0
at any element above X. A stretch of length m contributes m(m+1)/2 runs, which
is what the running addition accumulates.
Two boundaries to check. [3,3,3] with L=1, R=2 answers 0, since every maximum is
too large, and [5,5,5] with L=R=5 answers 6, since every one of the six runs
qualifies. The count reaches n(n+1)/2, which at n = 200000 is about
2 * 10^10 and overflows a 32-bit accumulator.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ value ≤ 1000000000` - `1 ≤ L ≤ R ≤ 1000000000`
Input
The first line contains three integers n, L and R.
The second line contains n space-separated integers.
Output
Print the number of contiguous non-empty runs whose maximum lies in [L, R].
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.