MEX vs MED (Codeforces 1744F)
Tags: Math, two pointers

You are given a permutation $$$p_1, p_2, \ldots, p_n$$$ of length $$$n$$$ of numbers $$$0, \ldots, n - 1$$$. Count the number of subsegments $$$1 \leq l \leq r \leq n$$$ of this permutation such that $$$mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$$$.$$$mex$$$ of $$$S$$$ is the smallest non-negative integer that does not occur in $$$S$$$. For example: $$$mex({0, 1, 2, 3}) = 4$$$ $$$mex({0, 4, 1, 3}) = 2$$$ $$$mex({5, 4, 0, 1, 2}) = 3$$$$$$med$$$ of the set $$$S$$$ is the median of the set, i.e. the element that, after sorting the elements in non-decreasing order, will be at position number $$$\left \lfloor{ \frac{|S| + 1}{2} } \right \rfloor$$$ (array elements are numbered starting from $$$1$$$ and here $$$\left \lfloor{v} \right \rfloor$$$ denotes rounding $$$v$$$ down.). For example: $$$med({0, 1, 2, 3}) = 1$$$ $$$med({0, 4, 1, 3}) = 1$$$ $$$med({5, 4, 0, 1, 2}) = 2$$$A sequence of $$$n$$$ numbers is called a permutation if it contains all the numbers from $$$0$$$ to $$$n - 1$$$ exactly once.

Input: The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4$$$), the number of test cases.The descriptions of the test cases follow.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the length of the permutation $$$p$$$.The second line of each test case contains exactly $$$n$$$ integers: $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \leq p_i \leq n - 1$$$), elements of permutation $$$p$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case print the answer in a single line: the number of subsegments $$$1 \leq l \leq r \leq n$$$ of this permutation such that $$$mex(p_l, p_{l+1}, \ldots, p_r) > med(p_l, p_{l+1}, \ldots, p_r)$$$.

Note: The first test case contains exactly one subsegment and $$$mex({0}) = 1 > med({0}) = 0$$$ on it.In the third test case, on the following subsegments: $$$[1, 0]$$$, $$$[0]$$$, $$$[1, 0, 2]$$$ and $$$[0, 2]$$$, $$$mex$$$ is greater than $$$med$$$.In the fourth test case, on the following subsegments: $$$[0, 2]$$$, $$$[0]$$$, $$$[0, 2, 1]$$$ and $$$[0, 2, 1, 3]$$$, $$$mex$$$ greater than $$$med$$$.

Sample Inputs:
8
1
0
2
1 0
3
1 0 2
4
0 2 1 3
5
3 1 0 2 4
6
2 0 4 1 3 5
8
3 7 2 6 0 1 5 4
4
2 0 1 3

Sample Outputs:
1
2
4
4
8
8
15
6

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

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    pos = [0] * n
    for (i, x) in enumerate(a):
        pos[x] = i
    (l, r) = (pos[0], pos[0])
    ans = 1
    for m in range(2, n + 1):
        i = pos[(m - 1) // 2]
        l = min(l, min(i, n - m))
        r = max(r, max(i, m - 1))
        ans += max(m - (r - l), 0)
    print(ans)
if __name__ == '__main__':
    for _ in range(int(input())):
        solve()

Solution (Python):
test_num = int(input())
for _ in range(test_num):
    n = int(input())
    pos = [0] * n
    data = list(map(int, input().split()))
    for i in range(n):
        x = data[i]
        pos[x] = i
    l = pos[0]
    r = pos[0]
    ans = 1
    for mex in range(1, n):
        next_pos = pos[mex]
        if l <= next_pos <= r:
            continue
        max_diff = mex * 2 - 1
        if next_pos < l:
            while l > next_pos:
                largest_r = min(l + max_diff, n - 1)
                ans += max(largest_r - r + 1, 0)
                l -= 1
        else:
            while r < next_pos:
                smallest_l = max(r - max_diff, 0)
                ans += max(l - smallest_l + 1, 0)
                r += 1
    print(ans)

Solution (Python):
def cf1744F():
    n = int(input())
    p = list(map(int, input().split()))
    d = [None] * n
    for (i, e) in enumerate(p):
        d[e] = i
    l = r = d[0]
    ans = 1
    for m in range(2, n + 1):
        i = d[(m - 1) // 2]
        l = min(l, min(i, n - m))
        r = max(r, max(i, m - 1))
        ans += max(m - (r - l), 0)
    print(ans)
t = int(input())
for i in range(t):
    cf1744F()