Click

You can see a similar problem Here . Check out it's editorial for solution details.

The first idea that comes to mind is an O(NlogN) algorithm to solve it, which is worse than O(N) but by a small margin.

Let x be the smallest element in the array and i be its index in the array (starting from 1). It's not hard to see that the amount of subarrays that contain x is equal to i*(N+1-i), where N is the index of the last element, and obviously the minimum of all these subarrays is x, so we can add x*i*(N+1-i) to the answer. Now, for every other y in the array, y cannot be the minimum for any subarray that contains x. So, we can split our array in two arrays [1,i-1] and [i+1,N] and solve the problem recursively, summing up the partial results in the end. Don't forget to fix the indexes at every step of the algorithm (the values for i and N will change depending on the current sub-array) At each step we have to find the minimum (this step will take O(logN) if you use a segment tree) and we have exactly N steps because at each step we remove one element from the array, so the final complexity is O(NlogN). If you choose to use sparse table instead of segment tree to perform the min queries, you can get min queries in O(1) but the cost to build the table is O(NlogN) so in the end of the day its all the same.

If you are confused i coded this: http://code.geeksforgeeks.org/paP9K7

Yes, it can be done in O(n).
For each position i, find the nearest element to its right whose value is less than that at i (if such element does not exist, consider this parameter to be n+1, where n is size of array). This whole process can be done in O(n) using stack.
Now start processing the array from right to left. Let DP[i] denote the sum of minimum of subarrays [i, j] such that i <= j <= n. Assume you are currently processing position i and the value of the above parameter is p. For all subarrays [i, j] such that i <= j < p, the minimum will be arr[i]. And for all subarrays [i, j] such that p <= j <= n, the sum of minimum of these subarrays has already been computed and stored in DP[p].
So, your formula becomes: DP[i] = (p-i)*arr[i] + DP[p]

UPD: This is the exact same problem, from a recent contest.
My code for the same can be found here.

I solved this problem using DSU, which isn't exactly O(N) but it's very efficient nevertheless. If we add elements in reverse order (from largest to smallest), we can keep blocks of already added contiguous elements using DSU. If current block goes from l to r and we just added A_i, then we must add to the answer (i - l + 1) * (r - i + 1) * A_i (all sub-blocks having A_i as minimum).

I was wondering how can these problem be solved.

1) Sum of averages of all the subarrays?

2) Sum of medians of all the subarrays?

Thanks in advance!

Thanks a lot for everyone for their great and smart solutions.

To keep you updated after thinking i found this O(n) solution that uses a Stack. It's based on counting the number along with every index as long as the value in the current index is great than it's value and when the current value is below the value in the stack i start removing from the stack.

#include<bits/stdc++.h>
#define mp make_pair

using namespace std;

int n;
int arr[100005];
stack< pair<int,int> > st;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    int curSum = 0, res = 0;
    for (int j = 0; j < n; j++)
    {
        if((!st.empty()) && arr[j] >= st.top().first)
        {
            curSum += arr[j];
            st.push(mp(arr[j], 1));
        }else
        {
            int cnt = 1;
            while((!st.empty()) && st.top().first > arr[j])
                cnt += st.top().second, curSum -= st.top().second * st.top().first,st.pop();
            st.push(mp(arr[j], cnt));
            curSum += cnt * arr[j];
        }
        res += curSum;
    }
    cout << res << endl;
    return 0;
}