691. Stretches Whose Largest Value Lands In a Band
Count the contiguous stretches whose LARGEST value is at least L and at most R.
2 1 4 3, L = 2, R = 3 -> 3
2 9 2 5 6, L = 2, R = 8 -> 7
1 5 1 5 1, L = 2, R = 5 -> 12
4 4 4, L = 1, R = 3 -> 0
## A two-sided condition, counted as a difference of one-sided ones
"The maximum is in [L, R]" is awkward because a value above R and a value below L fail
for opposite reasons. Split it:
answer = (stretches with maximum <= R) - (stretches with maximum <= L-1)
Every stretch with maximum at most L-1 also has maximum at most R, so the subtraction
removes exactly the ones that fall short, leaving exactly the ones in the band.
Turning a two-sided requirement into the difference of two one-sided ones is the move, and it is the same move problem 690 makes for counts rather than maximums.
## Counting stretches with maximum at most X
Every value in such a stretch must be at most X. So mark each position as allowed or not,
and the qualifying stretches are exactly the non empty stretches that lie entirely inside a
maximal RUN of allowed positions.
A run of length r contains r * (r + 1) / 2 of them. Accumulate it as you go:
run = 0; total = 0
for v in a:
if v <= X: run += 1; total += run
else: run = 0
Adding run at each allowed position counts the stretches ENDING there, which is the same
triangular total built one term at a time and never overflows partway.
## Why the maximum never has to be computed
Nothing in the sweep tracks a maximum. "Maximum at most X" is equivalent to "every value is
at most X", which is a per element test. The expensive-sounding quantity disappears.
Noticing that a condition on an aggregate is really a condition on each element is worth more than the counting itself.
## Boundaries
L = 1 makes the subtracted term zero, since no stretch has maximum at most 0.
When every value is above R the answer is 0, and 4 4 4 with R = 3 is that case.
A single value counts as 1 exactly when it lies in the band.
## Overflow
Both terms reach about 2 * 10^10 when the whole array is allowed, so the totals need
64 bits. Their DIFFERENCE may be small, which is what makes this easy to miss.
## Cost
Time O(n), two passes. Space O(1).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ L ≤ R ≤ 10^9` - `1 ≤ each value ≤ 10^9`
Input
The first line contains three integers n, L and R.
The second line contains n integers.
Output
Print one integer, the number of stretches whose largest value lies between L and R inclusive.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.