Add up every subarray's lowest value
Add the minimum of every contiguous subarray, by counting for each value how many subarrays it is the lowest of, using the nearest lower neighbours on each side. About 22 minutes.
Count the subarrays each value rules
An array of n values has about n squared over 2 subarrays, far too many to list. Flip the question. For each value, how many subarrays have it as their minimum? Its contribution to the total is the value times that count.
A subarray has this value as minimum if it stretches left and right without meeting anything lower. So the count is the number of choices for the left end times the number of choices for the right end.
left = 3 # choices for the start right = 2 # choices for the end count = left * right
2 can reach to the right over the 3, but not the 1: 1 choice left, 2 right, so 2 subarrays. Contribution: 4.
Ties and the stack
If two values are equal, a subarray containing both has two lowest values, but must be counted once. Make one side strict and the other not: on the left stop at a strictly lower value, on the right stop at a lower or equal one. Then the rightmost minimum owns the subarray.
Both distances come from monotonic stacks, one pass left to right and one right to left. The sum can be huge, so the answer is taken modulo 1,000,000,007.
MOD = 10**9 + 7 total = (total + 5 * 6) % MOD
In 3, 1, 2, 4, why does 1 rule 6 subarrays?
- AIts left end has 2 choices and its right end has 3, and 2 times 3 is 6
- BIt sits in the middle of 4 values
- CIt is the smallest, so it rules only 1 subarray
Show the answer
Its left end has 2 choices and its right end has 3, and 2 times 3 is 6. Nothing lower than 1 is in the way on either side.
Sum of subarray minimums
You get a list arr of whole numbers. For every run of consecutive values, take its smallest value, and return the sum of all of these. The answer can be very large, so return it modulo 1,000,000,007.
arr = [3, 1, 2, 4] → 17
1 ≤ length of arr ≤ 30,000 · 1 ≤ arr[i] ≤ 30,000