847. How Many Stretches Each Value Rules
Read n values. Every contiguous stretch (there are n * (n + 1) / 2 of them) is CREDITED to
one position: the position of its minimum, and if the minimum appears more than once in the
stretch, to the EARLIEST of those positions.
Print how many stretches each position is credited with, all n counts on one line separated by
single spaces. The counts add up to n * (n + 1) / 2, which is worth checking.
3 1 2 4 1 -> 1 8 2 1 3
2 2 2 2 -> 4 3 2 1
1 2 3 4 5 -> 5 4 3 2 1
In the second row every value is equal, so every stretch is credited to its first position: the four stretches starting at position 1 all go to position 1, the three starting at position 2 go to position 2, and so on.
## What has to be true for position i to be credited
A stretch [l, r] is credited to i when l <= i <= r and
* nothing in [l, i-1] is less than OR EQUAL TO a[i], because an equal value further left
would be the earliest minimum instead
* nothing in [i+1, r] is strictly less than a[i], since an equal value to the right is fine
So l may be anywhere after the last position at or below a[i], and r may be anywhere before
the next position strictly below a[i]:
count[i] = (i - previousSmallerOrEqual(i)) * (nextStrictlySmaller(i) - i)
## Why one side is loose and the other is strict
This is the single most important detail in the counting half of this topic. Both boundaries must be strict OR both loose and the sum comes out wrong: with both strict, a stretch containing two copies of its minimum is counted twice; with both loose, it is counted zero times.
Making the LEFT side loose and the RIGHT side strict picks the earliest minimum, which is exactly
the tie rule in the statement. Swapping them picks the latest minimum, which is also a consistent
rule, just a different one. The check is always the same: do the counts sum to n(n+1)/2?
Contrast problem 838, where BOTH sides are strict, because there the question is how far one bar can reach rather than how to share every stretch out among the bars.
## The stacks, and why they increase
Left to right, pop while the top value is strictly GREATER than a[i]; the survivor is
previousSmallerOrEqual(i). Right to left, pop while the top is greater than or equal to
a[i]; the survivor is nextStrictlySmaller(i).
Both stacks are increasing in value from the bottom up, because both questions look for something
smaller. The difference between the two passes is exactly one = sign, and that is the tie rule
living in the code.
## Size
Each count can reach about n^2 / 4, which is 10^10 at the limit, so the answers do not fit in
32 bits.
## Related problems
Problem 853 multiplies these counts by the values and adds them up, problem 852 keeps only the right half of the product, and problem 838 uses the both-strict convention for a different question.
## Cost
Time O(n), two stack passes. Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a[i] ≤ 10^9` - the answers can reach `10^10`, so they need 64 bits
Input
The first line contains one integer n.
The second line contains n integers a[0] ... a[n-1].
Output
Print n integers on one line, separated by single spaces: how many contiguous stretches are credited to each position, in input order. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.