$$$NlogN$$$ solution:

at first let's sort out array in reverse order, then we can iterate over array and using binary search find element that not greater than $$$a_i$$$ and add to answer (n — i + 1).

/*N log N solution: find for each L how many powerful subarrays are with start L. if [l,r] is not powerful subarray than [l,r+1] is not too. so do binary search: for fixed [l,r] we want to know is or not this subarray powerful subarray. Now you need just to find max element (measure with a) and second element with high (measure with b) and store if a/2 is more or uquel than b (for expample in array 5 2 62 23 this two elements will be 62 and 23). We can do this with RMQ(if you do not know this algo, you can study here:https://en.wikipedia.org/wiki/Range_minimum_query).*/ <-ignore

CORRECT SOLUTION:

N log N solution:

find for each l maximum r for that [l,r] will be powerfull array and A[l] will be max element. if we do not want [l,r] than [l,r+1] we do not want too. so we can find r with binary search: for fixed [l,r] store if max(A[l]..A[r])=A[l](find max with RMQ). if this is true, now we want to know is or not this subarray powerful subarray. Now you need just to find second element with high (measure with b) and store if A[l]/2 is more or uquel than b (for expample in array 5 2 62 23 second element with high will 23). We can do this with RMQ(if you do not know this algo, you can study here:https://en.wikipedia.org/wiki/Range_minimum_query). also do this for a left part of l too.

Here am I again with overkill solutions. (maybe not).

Let us calculate separately for each A[i] the number of power subarrays where A[i] is actually the maximum, and then sum these values to get the final answer.

So, we find some L and R, such as L < i < R, and both A[L] and A[R] are greater than A[i]. It is now obvious that all subarrays where A[i] is the maximum are located between L and R.

Okay. Now let's find the leftmost and the rightmost element between L and R, excluding A[i], say L' and R' which exceed A[i] / 2. It doesn't then require a lot of mental gymnastics to realize that ALL "valid" subarrays for A[i] are subarrays between L' and R' and necessarily contain i. Combinatorics tells that the answer is equal to ((R' — L' — 1) * (R' — L') — (i — L' — 1) * (i — L) — (R' — i — 1) * (R' — i)) / 2. (not sure if didn't confuse anything: it's basically all subarrays inside (L'; R') except those inside (L'; i) and (i; R').

In order to find leftmost and rightmost positions, you can use some data structure like an RMQ segment tree (where the most intuitive way to go is to binary search the positions — asymptotic complexity is n * log^2 which passes.)

Denote an element as 'dominating' a subarray if it is the maximum element of such subarray, and the subarray is a power array. We'll count how many subarrays each element dominates, then get our answer from that.

Keep a reverse-sorted array of (value, position) pairs. Now run a modified two-pointers algorithm, one pointing to the index $$$i$$$ we're focused on, the other pointing to the lowest (rightmost) index $$$j$$$ that satisfies $$$\frac{a_{i}}{2} < a_{j}$$$. Insert each element encountered with the second pointer into a balanced binary search tree (C++ set), only by their position. We don't care about the value because we know that each element at each index in our set will not be dominated by our current element.

Now for each element $$$a_{i}$$$ with the first pointer, we can use our set to find the first index $$$l$$$ to the left of $$$a_{i}$$$ that it doesn't dominate, and similarly to the right (call it $$$r$$$). If you $$$0$$$-index, insert elements $$$-1$$$ and $$$n$$$ into the set at the beginning. We now know that every subarray that overlaps with index $$$i$$$ between $$$l$$$ and $$$r$$$, exclusive, is dominated by $$$a_{i}$$$, and none others. With a little combinatorics, we can find that the number of such subarrays is $$$(i - l) * (r - i)$$$. Subtract $$$1$$$ because the single element isn't a power array, then add that to our answer. When we reach the end of the array with the first pointer, we're done.

This is $$$O(nlogn)$$$ because all we do is sort and each of the $$$O(n)$$$ operations on our set is $$$O(logn)$$$.

Can't you use the same strategy as in the All nearest smaller value problem?

I.e. we first compute for every element the number of power subarrays where it's the maximum and rightmost element. Call this $$$L[i]$$$ for the element at position $$$i$$$. We do the same for the case where the element is the leftmost element, call this $$$R[i]$$$. Then the total power subarrays for element $$$i$$$ where it's the maximum should be $$$L[i] + R[i] + L[i]*R[i]$$$.

The problem now boils down to finding $$$L[i]$$$ (and $$$R[i]$$$). Traverse the array from left to right, while maintaining a stack of already processed elements sorted in descending order. When we process element at position $$$i$$$ with value $$$v$$$, we keep popping the stack until we get an element $$$u > v$$$, then we push $$$u$$$ and $$$v$$$ onto the stack. While doing this we also make a note about the first element $$$w$$$ satisfying $$$w > v/2$$$, or rather we make a note of its index $$$j$$$. Because $$$L[i] = i-j-1$$$ (we can also imagine there is an element with infinity at position -1).

This process is $$$O(n)$$$ and can be done similarly to compute $$$R[i]$$$, so the overall complexity is also $$$O(n)$$$.

Or am I maybe overlooking something which yields the above solution incorrect?

Can you provide link to the problem? I have a NlogN solution in my mind and I want to test whether it is correct or not.