The link you uploaded have expired. Can you repost another version?

I have a divide and conquer solution but it’s too long to explain here. The brief explanation is this: divide the current segment to 2 subsegments. Calculate the answer of the problem for intervals lying in each left and right subsegments. Now we have to add the sum of the min.max of intervals which contain a part of the right and a part of the left subsegment. for each prefix of the right subsegment (mid, R) calculate these values and store them in some arrays(you can keep them in 1D arrays because we only need to know the rightmost point of the prefix): sum of minimums, sum of maximums, sum of min.max of (mid, mid), (mid, mid + 1), …, (mid, R). Now you can iterate over the L index lying in the left subsegment (and keeping values min and max of (L, mid)) and binary search to find the first R that sum(L, R) >= m and add the sums to the final answer.

Even if we had to sum up just minimums, I still don't have any idea.

Here's a draft to a solution: An observation is that r_min decreases while l decreases. So, we will try to calculate a value called sum_mul for every l, which is sum of (min * max) for all r in [r_min, n]. When we reduce l to l — 1, r_min is reduced to new_r_min. For all values from new_r_min to r_min, we can just calculate the answer for each of these positions — we can do this because there are only a total of n "insertions" into the [r_min, n] range. Now for the remaining values: if the (min[l...i] * max[r...i]) value changed when l--, this means that either min[l...i] changes, max[l...i] changes or both.

The idea is that, for all ranges [l1...r1] such that min[l...l1] = min[l...r1] and max[l...l1] = min[r...r1], and min[l...r1] and max[l...r1] is both changed, we will update the answer manually for that range. Then there are some positions left such that only max[l...i]/min[l...i] is changed; and we divide them into ranges such that max[l...i] or min[l...i] (depends on which value is being changed) of these values are previously equal, and then update manually for these ranges. It can be proven that there are only O(n) ranges considered (the logic behind this is similar to that of the monotonic queue).

About how to update on these ranges: the first type is quite trivial. For the second type, you will need to answer a query of the form get_sum for all min[l...i] with i from l1 to r1 (or the equivalent for max), while updating their values with range minimum queries. This can either be done with segment tree beats, or a conventional segment tree supporting the "set range to value i" query, which both works in O(n log n) (the reason why the latter works in O(n log n) is again the same as that of the monotonic queue).

We can solve this problem by Divide and Conquer.

$$$F(L, R)$$$ $$$=$$$ $$$\Sigma^{l \le R}_{l = L}$$$$$$\Sigma^{r \le R}_{r=l}$$$ $$$(sum^l_r >= m ? $$$$$$min^l_r$$$ $$$*$$$ $$$max^l_r$$$ $$$:$$$ $$$0)$$$.

We can divide this formula :

$$$mid = \lfloor(l + r)/2\rfloor$$$

$$$F(L, R)$$$ $$$=$$$ $$$F(L, mid)$$$ + $$$F(mid + 1, R)$$$ + $$$\Sigma^{l \le mid}_{l = L}$$$$$$\Sigma^{r \le R}_{r=mid + 1}$$$ $$$(sum^l_r >= m ? $$$$$$min^l_r$$$ $$$*$$$ $$$max^l_r$$$ $$$:$$$ $$$0)$$$.

If we can calculate ($$$\Sigma^{l \le mid}_{l = L}$$$$$$\Sigma^{r \le R}_{r=mid + 1}$$$ $$$(sum^l_r >= m ? $$$$$$min^l_r$$$ $$$*$$$ $$$max^l_r$$$ $$$:$$$ $$$0)$$$) we can solve this problem.

Let's divide this sum in four parts :

Sum of this $$$4$$$ parts is ($$$\Sigma^{l \le mid}_{l = L}$$$$$$\Sigma^{r \le R}_{r=mid + 1}$$$ $$$(sum^l_r >= m ? $$$$$$min^l_r$$$ $$$*$$$ $$$max^l_r$$$ $$$:$$$ $$$0)$$$).

Thats all. Answer is $$$F(1, n)$$$.

Time : $$$O(nlog^2n)$$$.

(Sorry for my bad english)