Max to the Right of Min (Codeforces 1849E)
Tags: DP, divide and conquer

You are given a permutation $$$p$$$ of length $$$n$$$ — an array, consisting of integers from $$$1$$$ to $$$n$$$, all distinct.Let $$$p_{l,r}$$$ denote a subarray — an array formed by writing down elements from index $$$l$$$ to index $$$r$$$, inclusive.Let $$$\mathit{maxpos}_{l,r}$$$ denote the index of the maximum element on $$$p_{l,r}$$$. Similarly, let $$$\mathit{minpos}_{l,r}$$$ denote the index of the minimum element on it.Calculate the number of subarrays $$$p_{l,r}$$$ such that $$$\mathit{maxpos}_{l,r} > \mathit{minpos}_{l,r}$$$.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of elements in the permutation.The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$). All $$$p_i$$$ are distinct.

Output: Print a single integer — the number of subarrays $$$p_{l,r}$$$ such that $$$\mathit{maxpos}_{l,r} > \mathit{minpos}_{l,r}$$$.


Sample Inputs:
3
1 2 3

6
5 3 6 1 4 2

10
5 1 6 2 8 3 4 10 9 7

Sample Outputs:
3

4

38

Solution (Python):
def t():
    n = int(input())
    L = [10000000.0] + list(map(int, input().split()))
    ans = 0
    valid = 0
    stmx = []
    stmn = []
    end = [None] * (n + 1)
    for i in range(n + 1):
        while stmx and L[i] > L[stmx[-1]]:
            if end[stmx[-1]]:
                (true_i, dec_i) = end[stmx[-1]]
                if dec_i < len(stmn) and stmn[dec_i] == true_i:
                    valid -= true_i - stmx[-1]
                    if dec_i == 0 or stmn[dec_i - 1] < stmx[-2]:
                        valid += true_i - stmx[-2]
                        end[stmx[-2]] = (true_i, dec_i)
                        end[true_i] = (stmx[-2], None)
                    else:
                        valid += true_i - stmn[dec_i - 1]
                        end[true_i] = (stmn[dec_i - 1], None)
            stmx.pop()
        while stmn and L[stmn[-1]] > L[i]:
            if end[stmn[-1]]:
                valid -= stmn[-1] - end[stmn[-1]][0]
            stmn.pop()
        stmx.append(i)
        stmn.append(i)
        end[i] = (i, len(stmn) - 1)
        ans += valid
    print(ans)
    return
if __name__ == '__main__':
    t()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
n = int(input())
a = [10000000.0] + list(map(int, input().split()))
ans = 0
valid = 0
inc = []
dec = []
end = [None] * (n + 1)
for i in range(n + 1):
    while inc and a[i] > a[inc[-1]]:
        (true_i, dec_i) = end[inc[-1]]
        if dec_i < len(dec) and dec[dec_i] == true_i:
            valid -= true_i - inc[-1]
            if dec_i == 0 or dec[dec_i - 1] < inc[-2]:
                valid += true_i - inc[-2]
                end[inc[-2]] = (true_i, dec_i)
                end[true_i] = (inc[-2], None)
            else:
                valid += true_i - dec[dec_i - 1]
                end[true_i] = (dec[dec_i - 1], None)
        inc.pop()
    while dec and a[i] < a[dec[-1]]:
        valid -= dec[-1] - end[dec[-1]][0]
        dec.pop()
    inc.append(i)
    dec.append(i)
    end[i] = (i, len(dec) - 1)
    ans += valid
print(ans)

Solution (Python):
import sys
ipt = sys.stdin.readline

def iin():
    return int(ipt())

def lmin():
    return list(map(int, ipt().split()))
inf = 1 << 30
N = iin()
P = lmin()
lmn = [-1] * N
rmn = [N] * N
st_mn = []
lmx = [-1] * N
rmx = [N] * N
st_mx = []
for (i, p) in enumerate(P):
    while st_mn and P[st_mn[-1]] > p:
        rmn[st_mn.pop()] = i
    if st_mn:
        lmn[i] = st_mn[-1]
    st_mn.append(i)
    while st_mx and P[st_mx[-1]] < p:
        rmx[st_mx.pop()] = i
    if st_mx:
        lmx[i] = st_mx[-1]
    st_mx.append(i)
ans = 0
for i in range(N):
    (l, r) = (lmn[i], rmn[i])
    if r - i <= i - l:
        ll = i
        for j in range(i + 1, r):
            ll = min(ll, lmx[j])
            if ll < l:
                ans += (i - l) * (r - j)
                break
            ans += i - ll
    else:
        rr = i
        ans += r - i - 1
        for j in range(i - 1, l, -1):
            rr = max(rr, rmx[j])
            if rr > r:
                break
            ans += r - rr
print(ans)