Thanks, it was a great question to solve.

Let me explain the solution. The approach used is similar to the way we build a segment tree. For this, given a range [l, r] if we want to obtain the result for the query in this range, we recursively compute the result of the same kind of query over the left half and the right half and then we need some way to combine the results from both halves to produce the result for the original range.

Now, the query is finding the sum of max * min over all subarrays in the range [l, r]. For this, we first compute the sum over all subarrays which lie completely in the left half and then compute the result for all subarrays that lie completely in the right half.

After this, what's left are the subarrays that span both the halves.

For this we need some information from the results of both halves. From here on, prefix means a prefix of the right half and suffix means a suffix of the left half. All subarrays which span can be represented as a combination of a non empty prefix and a non empty suffix. pre[i] means a prefix of the first (i + 1) elems in the right half [0 .. i] and suf[i] means a suffix of the last (i+1) elems in the left half.

Let's compute a few arrays:

1. premn, s.t. premn[i] is the min element in the prefix upto the ith element.

2. premx, s.t. premx[i] is the max element in the prefix upto the ith element.

3. sufmn, s.t. sufmn[i] is the min element in the suffix upto the ith element(remember, in case of suffix the ith element means the ith element from the back, assuming elements start from 0)

4. sufmx, s.t. sufmx[i] is the max element in the suffix upto the ith element.

5. mxsum, s.t. mxsum[i] is the sum of the max elems in the prefixes upto the ith element, i.e., sum of premx[0] .. premx[i]

6. mnsum, similar to the one above but with the sum of the min elems

7. mnmxsum, s.t. mnmxsum[i] is the sum of max * min elems in the prefixes upto the ith element, i.e., sum of premx[0] * premn[0] .. premn[i] * premx[i]

Now iterate over the original indices in the left half starting from the back with indices varying from m down to l. For every index i, we will compute the sum over subarrays of the form Ai .. Aj, with index j lying in the right half. We will consider the max. length upto which sufmx[i] is the max element in the prefix (mxval) and also the max. length upto which sufmn[i] is the min element in the prefix (mnval).

Now consider this:

1. For j in range [0, min(mxval, mnval)-1], we know that for all subarrays of the form Ai .. A(m+1+j), the min element is sufmn[i] and the max element is sufmx[i]. Let x = min(mxval, mnval). The total no. of subarrays in this case is x. So, we add x * sufmn[i] * sufmx[i] to the answer.

2. For j in range [max(mnval, mxval), r-m-1], we know that for all subarrays of the form Ai .. A(m+1+j), neither sufmn[i] is the min element, nor sufmx[i] is the max. element. Let x = min(mxval, mnval). So, here the min. and the max. elements are premn[j] and premx[j] respectively. So, the product of min * max in the range [x, r-m-1] can be obtained by using the values from mnmxsum as mnmxsum[r-m-1] — mnmxsum[x-1]. So, we add mnmxsum[r-m-1] — mnmxsum[x-1] to the answer.

3. For j in range [min(mxval, mnval), max(mxval, mnval)-1], we know that for all subarrays of the form Ai .. A(m+1+j):

   3a. if mxptr > mnptr, then sufmx[i] is the max. element but sufmn[i] is not the min. element. So, the min element for a particular value of j is premn[j]. In the sum of products of max * min, we can take max common, since this is the same and we are left with the sum of the premn's in the range, which can be obtained using mnsum. So, here, we add sufmx[i] * (mnsum[mxptr-1] — mnsum[mnptr-1]). 3b. if mxptr <= mnptr, this is similar to the above case with mx's and mn's interchanged.

The complexity for this is found by the recurrence: T(n) = 2T(n / 2) + O(n), which comes out to be O(n lg n). For implementing check out the code given in the editorial section of the problem.

Hope this helps you understand the solution to the problem.