Range Sorting (Hard Version) (Codeforces 1828D2)
Tags: Greedy, binary search

The only difference between this problem and the easy version is the constraints on $$$t$$$ and $$$n$$$.You are given an array $$$a$$$, consisting of $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$. Define the beauty of an array $$$p_1, p_2, \ldots p_k$$$ as the minimum amount of time needed to sort this array using an arbitrary number of range-sort operations. In each range-sort operation, you will do the following:   Choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le k$$$).  Sort the subarray $$$p_l, p_{l + 1}, \ldots, p_r$$$ in $$$r - l$$$ seconds. Please calculate the sum of beauty over all subarrays of array $$$a$$$.A subarray of an array is defined as a sequence of consecutive elements of the array.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line of each test case consists of $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$). It is guaranteed that all elements of $$$a$$$ are pairwise distinct.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, output the sum of beauty over all subarrays of array $$$a$$$.

Note: In the first test case:   The subarray $$$[6]$$$ is already sorted, so its beauty is $$$0$$$.  The subarray $$$[4]$$$ is already sorted, so its beauty is $$$0$$$.  You can sort the subarray $$$[6, 4]$$$ in one operation by choosing $$$l = 1$$$ and $$$r = 2$$$. Its beauty is equal to $$$1$$$.  The sum of beauty over all subarrays of the given array is equal to $$$0 + 0 + 1 = 1$$$.In the second test case:   The subarray $$$[3]$$$ is already sorted, so its beauty is $$$0$$$.  The subarray $$$[10]$$$ is already sorted, so its beauty is $$$0$$$.  The subarray $$$[6]$$$ is already sorted, so its beauty is $$$0$$$.  The subarray $$$[3, 10]$$$ is already sorted, so its beauty is $$$0$$$.  You can sort the subarray $$$[10, 6]$$$ in one operation by choosing $$$l = 1$$$ and $$$r = 2$$$. Its beauty is equal to $$$2 - 1 = 1$$$.  You can sort the subarray $$$[3, 10, 6]$$$ in one operation by choosing $$$l = 2$$$ and $$$r = 3$$$. Its beauty is equal to $$$3 - 2 = 1$$$.  The sum of beauty over all subarrays of the given array is equal to $$$0 + 0 + 0 + 0 + 1 + 1 = 2$$$.

Sample Inputs:
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18

Sample Outputs:
1
2
8
16
232

Solution (Python):
import sys
import collections
import heapq
input = sys.stdin.readline

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    kpos = [-1] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and a[i] < a[stack[-1]]:
            curr = stack.pop()
            if kpos[curr] == -1:
                kpos[curr] = i
        stack.append(i)
    ypos = [n] * n
    stack = []
    for i in range(n):
        while stack and a[i] < a[stack[-1]]:
            curr = stack.pop()
            if ypos[curr] == n:
                ypos[curr] = i
        stack.append(i)
    xpos = [-1] * n
    stack = []
    second = []
    for i in range(n - 1, -1, -1):
        while second and a[i] > a[second[-1]]:
            curr = second.pop()
            if xpos[curr] == -1:
                xpos[curr] = i
        temp = []
        while stack and a[i] < a[stack[-1]]:
            curr = stack.pop()
            if xpos[curr] == -1:
                temp.append(curr)
        stack.append(i)
        second += temp[:]
    res = 0
    for i in range(n):
        res += (kpos[i] - xpos[i]) * (ypos[i] - i)
    print((n - 1) * n * (n + 1) // 6 - res)
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def testcase():
    n = int(input())
    a = list(map(int, input().split()))
    (x, k, y) = ([-1] * n, [-1] * n, [n] * n)
    (first, second) = ([], [])
    for i in range(n - 1, -1, -1):
        while second and a[second[-1]] < a[i]:
            x[second.pop()] = i
        while first and a[first[-1]] > a[i]:
            p = first.pop()
            second.append(p)
            k[p] = i
        y[i] = first[-1] if first else n
        first.append(i)
    print(sum([(i + 1) * i // 2 - (k[i] - x[i]) * (y[i] - i) for i in range(n)]))
if __name__ == '__main__':
    for _ in range(int(input())):
        testcase()

Solution (Python):
import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def testcase():
    n = int(input())
    L = list(map(int, input().split()))
    first = []
    second = []
    (k, y, x) = ([-1] * n, [n] * n, [-1] * n)
    for i in range(n - 1, -1, -1):
        while second and L[second[-1]] < L[i]:
            x[second.pop()] = i
        while first and L[first[-1]] > L[i]:
            p = first[-1]
            del first[-1]
            second.append(p)
            k[p] = i
        y[i] = first[-1] if first else n
        first.append(i)
    print(sum((i * (i + 1) // 2 - (k[i] - x[i]) * (y[i] - i) for i in range(n))))
if __name__ == '__main__':
    for _ in range(int(input())):
        testcase()