Decinc Dividing (Codeforces 1694F)
Tags: Greedy, data structures

Let's call an array $$$a$$$ of $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$ Decinc if $$$a$$$ can be made increasing by removing a decreasing subsequence (possibly empty) from it. For example, if $$$a = [3, 2, 4, 1, 5]$$$, we can remove the decreasing subsequence $$$[a_1, a_4]$$$ from $$$a$$$ and obtain $$$a = [2, 4, 5]$$$, which is increasing.You are given a permutation $$$p$$$ of numbers from $$$1$$$ to $$$n$$$. Find the number of pairs of integers $$$(l, r)$$$ with $$$1 \le l \le r \le n$$$ such that $$$p[l \ldots r]$$$ (the subarray of $$$p$$$ from $$$l$$$ to $$$r$$$) is a Decinc array. 

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)  — the size of $$$p$$$.The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ are distinct)  — elements of the permutation.

Output: Output the number of pairs of integers $$$(l, r)$$$ such that $$$p[l \ldots r]$$$ (the subarray of $$$p$$$ from $$$l$$$ to $$$r$$$) is a Decinc array. $$$(1 \le l \le r \le n)$$$

Note: In the first sample, all subarrays are Decinc.In the second sample, all subarrays except $$$p[1 \ldots 6]$$$ and $$$p[2 \ldots 6]$$$ are Decinc.

Sample Inputs:
3
2 3 1

6
4 5 2 6 1 3

10
7 10 1 8 3 9 2 4 6 5

Sample Outputs:
6

19

39

Solution (Python):
input = __import__('sys').stdin.readline
n = int(input())
a = list(map(int, input().split())) + [n + 1]
cache = {}

def check(i, u, d):
    keys = []
    j = i
    while j + 1 <= n:
        key = (j, u, d)
        v = cache.get(key, -1)
        if v != -1:
            j = v
            break
        keys.append(key)
        if u < a[j] < d:
            if a[j] < a[j + 1]:
                u = max(u, a[j])
            elif a[j] > a[j + 1]:
                d = min(d, a[j])
        elif u < a[j]:
            u = a[j]
        elif d > a[j]:
            d = a[j]
        else:
            break
        j += 1
    for key in keys:
        cache[key] = j
    return j
ans = 0
for i in range(n):
    u = 0
    d = n + 1
    j = check(i, u, d)
    ans += j - i
print(ans)

Solution (Python):
input = __import__('sys').stdin.readline
n = int(input())
a = list(map(int, input().split())) + [n + 1]
B = n + 2
cache = {}

def check(i, u, d):
    keys = []
    j = i
    while j + 1 <= n:
        key = (u * B + d) * B + j
        v = cache.get(key, -1)
        if v != -1:
            j = v
            break
        keys.append(key)
        if u < a[j] < d:
            if a[j] < a[j + 1]:
                u = max(u, a[j])
            elif a[j] > a[j + 1]:
                d = min(d, a[j])
        elif u < a[j]:
            u = a[j]
        elif d > a[j]:
            d = a[j]
        else:
            break
        j += 1
    for key in keys:
        cache[key] = j
    return j
ans = 0
for i in range(n):
    u = 0
    d = n + 1
    j = check(i, u, d)
    ans += j - i
print(ans)

Solution (Python):
input = __import__('sys').stdin.readline
n = int(input())
a = list(map(int, input().split())) + [n + 1]
cache = {}

def check(i, u, d):
    keys = []
    j = i
    while j + 1 <= n:
        key = (j, u, d)
        v = cache.get(key, -1)
        if v != -1:
            j = v
            break
        keys.append(key)
        if u < a[j] < d:
            if a[j] < a[j + 1]:
                u = max(u, a[j])
            elif a[j] > a[j + 1]:
                d = min(d, a[j])
        elif u < a[j]:
            u = a[j]
        elif d > a[j]:
            d = a[j]
        else:
            break
        j += 1
    for key in keys:
        cache[key] = j
    return j
ans = 0
for i in range(n):
    u = 0
    d = n + 1
    j = check(i, u, d)
    ans += j - i
print(ans)