Given an array $a_1, a_2, ..., a_n$ and $Q$ queries, each includes 2 integers $u < v$. For each query, you must calculate $\sum\limits_{u \leq l \leq r \leq v}{min(a_l, a_{l+1}, ..., a_r)}$.
As $n = 10^5$, I want to find an solution in $O(n \log n)$ or $O(n \sqrt{n})$ or less.
But I have no efficient approach for this problem.
If $Q = 1, u = 1, v = n$. For each $i$ from $1$ to $n$, call $i_1$ be the largest integer less than $i$ and $a_{i_1} > a_i$ and $i_2$ be the smallest integer greater than $i$ and $a_{i_2} > a_i$. (To find $i_1, i_2$, we use stacks)
So the answer is $\sum\limits_{i=1}^{n}{a_i \times (i-i_1+1)\times (i-i_2+1)}$
But if $Q > 1$ we will need so many stacks.
Is there any efficient solution to this problem?
I believe this is not the right place to ask this question, try one of the competitive programming sites, as for your problem you are nearly there, try to think about what happens to the contribution of each index when you set a bound (u, v), there are four situations that arise from $u \leq i_1$ and $i_2 \leq v$, you will probably need a data strucutre to speed up your algorithm (e.g. a segment tree, or persistent segment tree)
PS: I hope this question is not from an ongoing competition.