Auto comment: topic has been updated by akshit.lite (previous revision, new revision, compare).

Auto comment: topic has been updated by akshit.lite (previous revision, new revision, compare).

Sorry, misunderstood the problem statement.

Lets focus on each element of the array. For a fixed element, we wonder how many times it will be added to our total sum. Clearly, for every subarray that includes this element as the maximum, we will add it. Let our fixed element be A[x]. Then if i is the last index on the left of x such that A[i] < A[x], and j is the last index on the right of x such that A[j] < A[x], then A[x] will be added exactly (x-i+1)(j-x+1) times(you can use combinatorics to prove this). Note that if we have A[i]=A[x] or A[j]=A[x], we can count this subarray as well, but will have to subtract out some numbers at the end because we overcounted(you can use a map to store counts of each number, then do some combinatorics).

Now the only question is, how do we calculate i and j? Let's generate j first. Iterate through the array from left to right and keep track of a multiset of elements we have seen so far. When we encounter an element, let's remove all smaller elements possible from the multiset and set their j values to be this index. Then add this element to the multiset and move on. We can do a similar thing traversing the array right to left to compute the i values.

Since we iterate and use multiset for deletion, our complexity ends up being O(N log N).

I solved this problem using fenwick tree. If r[n] is the result, you can figure out for each number in input array which indexes of r it affects. Each number in input array will form a pattern which can be easily processed and queried by fenwick tree.

can it can be solved in nlogn by binary search by first taking cumilative sum??

It can be solved in O(n):

http://pastebin.com/xeUpgjTe

For each i = 1, 2, ..., n we can find maximal p < i and minimal q > i such that a[p] >= a[i], a[q] > a[i] or p = 0 or q = n+1 (on left we have >= and on right > to not count twice the same interval). Then, if we fixed i we can observe that, for intervals of length 1, 2, 3, ... min(i-p, q-i)-1 we add to result a[i]*interval_length, for intervals of length min(i-p, q-i), ..., max(i-p, q-i)-1 we add min(i-p, q-i)*a[i] and for intervals of length max(i-p, q-i), ..., q-p-1 we add (q-p-interval_length)*a[i]. We want to have O(n) complexity, so in first case (when intervals have length < min(i-p, q-i)) we can add a[i] to some variable (in my code ,,sum"), and add a[i] to tab[min(i-p, q-i)], then when we will count answer for intervals of length i we will subtract tab[i] from sum and next add to result sum*i. Similar things we can do in second and third case.