Array Collapse (Codeforces 1913D)
Tags: DP, divide and conquer

You are given an array $$$[p_1, p_2, \dots, p_n]$$$, where all elements are distinct.You can perform several (possibly zero) operations with it. In one operation, you can choose a contiguous subsegment of $$$p$$$ and remove all elements from that subsegment, except for the minimum element on that subsegment. For example, if $$$p = [3, 1, 4, 7, 5, 2, 6]$$$ and you choose the subsegment from the $$$3$$$-rd element to the $$$6$$$-th element, the resulting array is $$$[3, 1, 2, 6]$$$.An array $$$a$$$ is called reachable if it can be obtained from $$$p$$$ using several (maybe zero) aforementioned operations. Calculate the number of reachable arrays, and print it modulo $$$998244353$$$.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Each test case consists of two lines. The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$). The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le 10^9$$$).Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, print one integer — the number of reachable arrays, taken modulo $$$998244353$$$.


Sample Inputs:
3
2
2 1
4
2 4 1 3
5
10 2 6 3 4

Sample Outputs:
2
6
12

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

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, p) = (readInt(), readList())
    (ns, st) = ([n] * n, [])
    for i in range(n):
        while st and p[st[-1]] > p[i]:
            ns[st.pop()] = i
        st.append(i)
    ss = [0] * (n + 2)
    (dp0, dp1) = ([0] * (n + 1), [0] * (n + 1))
    ss[n - 1] = dp0[n - 1] = dp1[n - 1] = 1
    ss[n] = -1
    for i in range(n - 2, -1, -1):
        dp0[i] = (ss[i + 1] - ss[ns[i]] + dp1[ns[i]]) % m
        dp1[i] = (dp0[i] + dp1[ns[i]]) % m
        ss[i] += (ss[i + 1] + dp0[i]) % m
    return dp1[0]
m = 998244353
for _ in range(int(input())):
    print(solve())

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

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, p) = (readInt(), readList())
    (ns, st) = ([n] * n, [])
    for i in range(n):
        while st and p[st[-1]] > p[i]:
            ns[st.pop()] = i
        st.append(i)
    ss = [0] * (n + 2)
    (dp0, dp1) = ([0] * (n + 1), [0] * (n + 1))
    ss[n - 1] = dp0[n - 1] = dp1[n - 1] = 1
    ss[n] = -1
    for i in range(n - 2, -1, -1):
        dp0[i] = (ss[i + 1] - ss[ns[i]] + dp1[ns[i]]) % m
        dp1[i] = (dp0[i] + dp1[ns[i]]) % m
        ss[i] += (ss[i + 1] + dp0[i]) % m
    return dp1[0]
m = 998244353
for _ in range(int(input())):
    print(solve())

Solution (Python):
import sys
input = sys.stdin.readline
mod = 998244353
for t in range(int(input())):
    n = map(int, input().split())
    a = list(map(int, input().split()))
    b = [(-1, 1), (a[0], 1, 1)]
    s = 1
    for ele in a[1:]:
        x = y = 0
        while ele < b[-1][0]:
            (i, j) = b.pop()[1:]
            (x, y) = ((x + i) % mod, (y + j) % mod)
        b.append((ele, (s + y) % mod, (x + y) % mod))
        s = (2 * s - x + y) % mod
    print(s)