Moscow Gorillas (Codeforces 1793D)
Tags: Greedy, two pointers

In winter, the inhabitants of the Moscow Zoo are very bored, in particular, it concerns gorillas. You decided to entertain them and brought a permutation $$$p$$$ of length $$$n$$$ to the zoo.A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ occurs twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but $$$4$$$ is present in the array).The gorillas had their own permutation $$$q$$$ of length $$$n$$$. They suggested that you count the number of pairs of integers $$$l, r$$$ ($$$1 \le l \le r \le n$$$) such that $$$\operatorname{MEX}([p_l, p_{l+1}, \ldots, p_r])=\operatorname{MEX}([q_l, q_{l+1}, \ldots, q_r])$$$.The $$$\operatorname{MEX}$$$ of the sequence is the minimum integer positive number missing from this sequence. For example, $$$\operatorname{MEX}([1, 3]) = 2$$$, $$$\operatorname{MEX}([5]) = 1$$$, $$$\operatorname{MEX}([3, 1, 2, 6]) = 4$$$.You do not want to risk your health, so you will not dare to refuse the gorillas.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the permutations length.The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the elements of the permutation $$$p$$$.The third line contains $$$n$$$ integers $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le n$$$) — the elements of the permutation $$$q$$$.

Output: Print a single integer — the number of suitable pairs $$$l$$$ and $$$r$$$.

Note: In the first example, two segments are correct – $$$[1, 3]$$$ with $$$\operatorname{MEX}$$$ equal to $$$4$$$ in both arrays and $$$[3, 3]$$$ with $$$\operatorname{MEX}$$$ equal to $$$1$$$ in both of arrays.In the second example, for example, the segment $$$[1, 4]$$$ is correct, and the segment $$$[6, 7]$$$ isn't correct, because $$$\operatorname{MEX}(5, 4) \neq \operatorname{MEX}(1, 4)$$$.

Sample Inputs:
3
1 3 2
2 1 3

7
7 3 6 2 1 5 4
6 7 2 5 3 1 4

6
1 2 3 4 5 6
6 5 4 3 2 1

Sample Outputs:
2

16

11

Solution (Python):
import sys

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    p = list(map(int, inp().split()))
    q = list(map(int, inp().split()))
    pi = [None] * (n + 1)
    qi = [None] * (n + 1)
    for i in range(n):
        pi[p[i]] = i
        qi[q[i]] = i
    x = pi[1]
    y = qi[1]
    if x > y:
        (x, y) = (y, x)
    res = 0
    if x >= 1:
        res += x * (x + 1) // 2
    if n - 1 - y >= 1:
        res += (n - y - 1) * (n - y) // 2
    if y - x - 1 >= 1:
        res += (y - x - 1) * (y - x) // 2
    l = x
    r = y
    for i in range(2, n):
        x = pi[i]
        y = qi[i]
        if x > y:
            (x, y) = (y, x)
        if not (x >= l and x <= r or (y >= l and y <= r)):
            if y < l:
                u = l - y
            elif x < l:
                u = l - x
            else:
                u = l + 1
            if x > r:
                v = x - r
            elif y > r:
                v = y - r
            else:
                v = n - r
            res += u * v
        l = min(l, x)
        r = max(r, y)
    print(res + 1)

def main():
    solve()
if __name__ == '__main__':
    main()

Solution (Python):
from math import sqrt

def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m1 = [0] * (n + 1)
    m2 = [0] * (n + 1)
    for i in range(n):
        m1[a[i]] = i
        m2[b[i]] = i
    l = -1
    r = n
    mini = min(m1[1], m2[1])
    maxi = max(m1[1], m2[1])
    ans = (n - 1 - maxi) * (n - maxi) // 2 + mini * (mini + 1) // 2 + max(0, (maxi - mini - 1) * (maxi - mini) // 2)
    l = mini
    r = maxi
    for mex in range(2, n + 1):
        mini = min(m1[mex], m2[mex])
        maxi = max(m1[mex], m2[mex])
        if maxi < l:
            ans += (l - maxi) * (n - r)
        elif r < mini:
            ans += (mini - r) * (l + 1)
        elif mini < l and maxi > r:
            ans += (l - mini) * (maxi - r)
        l = min(l, mini)
        r = max(r, maxi)
    print(ans + 1)
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def getint():
    return int(input())

def getfloat():
    return float(input())

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

def getfloats():
    return list(map(float, input().split()))

def getcomb(O00OO00O0O00O00OO):
    return O00OO00O0O00O00OO * (O00OO00O0O00O00OO + 1) // 2

def answer():
    O00O00OO0OOO0OOOO = getint()
    OO00OOO0OO0OOOO0O = getints()
    OOOO0O0O00O000000 = getints()
    O0OOO00OO00OOO00O = [0] * (O00O00OO0OOO0OOOO + 1)
    O0O000O00OOOO0OOO = [0] * (O00O00OO0OOO0OOOO + 1)
    for (OO0OOOOOO00OO0OO0, _O000OOO00OO00OOO0) in enumerate(OO00OOO0OO0OOOO0O):
        O0OOO00OO00OOO00O[_O000OOO00OO00OOO0] = OO0OOOOOO00OO0OO0
    for (OO0OOOOOO00OO0OO0, _O00OO0O000OOOO0O0) in enumerate(OOOO0O0O00O000000):
        O0O000O00OOOO0OOO[_O00OO0O000OOOO0O0] = OO0OOOOOO00OO0OO0
    O0000OO00OOO000O0 = min(O0OOO00OO00OOO00O[1], O0O000O00OOOO0OOO[1])
    O0O0O00OO0OOO00O0 = max(O0OOO00OO00OOO00O[1], O0O000O00OOOO0OOO[1])
    OO000OOO000OO0000 = getcomb(O0000OO00OOO000O0) + getcomb(O0O0O00OO0OOO00O0 - O0000OO00OOO000O0 - 1) + getcomb(O00O00OO0OOO0OOOO - 1 - O0O0O00OO0OOO00O0)
    for OO0OOOOOO00OO0OO0 in range(2, O00O00OO0OOO0OOOO):
        if O0000OO00OOO000O0 <= O0OOO00OO00OOO00O[OO0OOOOOO00OO0OO0] <= O0O0O00OO0OOO00O0 or O0000OO00OOO000O0 <= O0O000O00OOOO0OOO[OO0OOOOOO00OO0OO0] <= O0O0O00OO0OOO00O0:
            O0000OO00OOO000O0 = min(O0OOO00OO00OOO00O[OO0OOOOOO00OO0OO0], O0000OO00OOO000O0, O0O000O00OOOO0OOO[OO0OOOOOO00OO0OO0])
            O0O0O00OO0OOO00O0 = max(O0OOO00OO00OOO00O[OO0OOOOOO00OO0OO0], O0O0O00OO0OOO00O0, O0O000O00OOOO0OOO[OO0OOOOOO00OO0OO0])
            continue
        OO000O000O0000O00 = -1
        O0OOOO00OO0O0000O = O00O00OO0OOO0OOOO
        if O0OOO00OO00OOO00O[OO0OOOOOO00OO0OO0] < O0000OO00OOO000O0:
            OO000O000O0000O00 = max(OO000O000O0000O00, O0OOO00OO00OOO00O[OO0OOOOOO00OO0OO0])
        if O0OOO00OO00OOO00O[OO0OOOOOO00OO0OO0] > O0O0O00OO0OOO00O0:
            O0OOOO00OO0O0000O = min(O0OOOO00OO0O0000O, O0OOO00OO00OOO00O[OO0OOOOOO00OO0OO0])
        if O0O000O00OOOO0OOO[OO0OOOOOO00OO0OO0] < O0000OO00OOO000O0:
            OO000O000O0000O00 = max(OO000O000O0000O00, O0O000O00OOOO0OOO[OO0OOOOOO00OO0OO0])
        if O0O000O00OOOO0OOO[OO0OOOOOO00OO0OO0] > O0O0O00OO0OOO00O0:
            O0OOOO00OO0O0000O = min(O0OOOO00OO0O0000O, O0O000O00OOOO0OOO[OO0OOOOOO00OO0OO0])
        OO000OOO000OO0000 += (O0000OO00OOO000O0 - OO000O000O0000O00) * (O0OOOO00OO0O0000O - O0O0O00OO0OOO00O0)
        O0000OO00OOO000O0 = min(O0OOO00OO00OOO00O[OO0OOOOOO00OO0OO0], O0000OO00OOO000O0, O0O000O00OOOO0OOO[OO0OOOOOO00OO0OO0])
        O0O0O00OO0OOO00O0 = max(O0OOO00OO00OOO00O[OO0OOOOOO00OO0OO0], O0O0O00OO0OOO00O0, O0O000O00OOOO0OOO[OO0OOOOOO00OO0OO0])
    print(OO000OOO000OO0000 + 1)
T = 1
for i in range(T):
    answer()