Field Should Not Be Empty (Codeforces 1905F)
Tags: Others, divide and conquer

You are given a permutation$$$^{\dagger}$$$ $$$p$$$ of length $$$n$$$.We call index $$$x$$$ good if for all $$$y < x$$$ it holds that $$$p_y < p_x$$$ and for all $$$y > x$$$ it holds that $$$p_y > p_x$$$. We call $$$f(p)$$$ the number of good indices in $$$p$$$. You can perform the following operation: pick $$$2$$$ distinct indices $$$i$$$ and $$$j$$$ and swap elements $$$p_i$$$ and $$$p_j$$$. Find the maximum value of $$$f(p)$$$ after applying the aforementioned operation exactly once.$$$^{\dagger}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input: Each test consists of multiple test cases. The first line of contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the permutation $$$p$$$.The second line of each test case contain $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the elements of the permutation $$$p$$$.It is guaranteed that sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer — the maximum value of $$$f(p)$$$ after performing the operation exactly once.

Note: In the first test case, $$$p = [1,2,3,4,5]$$$ and $$$f(p)=5$$$ which is already maximum possible. But must perform the operation anyway. We can get $$$f(p)=3$$$ by choosing $$$i=1$$$ and $$$j=2$$$ which makes $$$p = [2,1,3,4,5]$$$.In the second test case, we can transform $$$p$$$ into $$$[1,2,3,4,5]$$$ by choosing $$$i=1$$$ and $$$j=2$$$. Thus $$$f(p)=5$$$.

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

Sample Outputs:
3
5
2
3
2

Solution (Python):
import sys

def inp():
    return sys.stdin.readline()

def LII1():
    return [int(x) - 1 for x in inp().split()]

def II():
    return int(inp())

def delete_segment(v):
    global current_cover, cover_size
    cover_size -= 1
    if next_cover[v] == v:
        last_cover[v] = -1
        next_cover[v] = -1
        current_cover = -1
    else:
        if current_cover == v:
            current_cover = next_cover[v]
        next_cover[last_cover[v]] = next_cover[v]
        last_cover[next_cover[v]] = last_cover[v]
    return

def add_segment(v):
    global current_cover, cover_size
    cover_size += 1
    if current_cover == -1:
        current_cover = v
        next_cover[v] = v
        last_cover[v] = v
    else:
        n = next_cover[current_cover]
        next_cover[v] = n
        next_cover[current_cover] = v
        last_cover[v] = current_cover
        last_cover[n] = v
    return
for _ in range(int(inp())):
    n = II()
    p = LII1()
    assert len(p) == n
    if all((p[i] == i for i in range(n))):
        print(n - 2)
        continue
    p_inv = n * [None]
    for i in range(n):
        p_inv[p[i]] = i
    cover_size = 0
    current_cover = -1
    next_cover = n * [-1]
    last_cover = n * [-1]
    uncovered_count = 0
    max_covered_2_count = -1
    covered_2 = None
    for i in range(n):
        assert cover_size % 2 == 0
        if p[i] == i:
            if cover_size == 0:
                uncovered_count += 1
            elif cover_size == 2:
                covered_2_count += 1
            continue
        last_cover_size = cover_size
        last_covered_2 = covered_2
        if p[i] < i:
            delete_segment(i)
        else:
            add_segment(i)
        if p_inv[i] < i:
            delete_segment(p_inv[i])
        else:
            add_segment(p_inv[i])
        if cover_size == 2:
            s1 = current_cover
            s2 = next_cover[current_cover]
            covered_2 = (min(s1, s2), max(s1, s2))
        if last_cover_size == 0 and cover_size == 2:
            covered_2_count = 1
        elif last_cover_size == 2 and cover_size == 0:
            covered_2_count += 1
            max_covered_2_count = max(max_covered_2_count, covered_2_count)
        elif cover_size == 2 and covered_2 != last_covered_2:
            max_covered_2_count = max(max_covered_2_count, covered_2_count)
            covered_2_count = 0
    assert cover_size == 0
    print(uncovered_count + max_covered_2_count)

Solution (Python):
import sys

def inp():
    return sys.stdin.readline()

def LII1():
    return [int(x) - 1 for x in inp().split()]

def II():
    return int(inp())

def delete_segment(v):
    global current_cover, cover_size
    cover_size -= 1
    if next_cover[v] == v:
        last_cover[v] = -1
        next_cover[v] = -1
        current_cover = -1
    else:
        if current_cover == v:
            current_cover = next_cover[v]
        next_cover[last_cover[v]] = next_cover[v]
        last_cover[next_cover[v]] = last_cover[v]
    return

def add_segment(v):
    global current_cover, cover_size
    cover_size += 1
    if current_cover == -1:
        current_cover = v
        next_cover[v] = v
        last_cover[v] = v
    else:
        n = next_cover[current_cover]
        next_cover[v] = n
        next_cover[current_cover] = v
        last_cover[v] = current_cover
        last_cover[n] = v
    return
for _ in range(int(inp())):
    n = II()
    p = LII1()
    assert len(p) == n
    if all((p[i] == i for i in range(n))):
        print(n - 2)
        continue
    p_inv = n * [None]
    for i in range(n):
        p_inv[p[i]] = i
    cover_size = 0
    current_cover = -1
    next_cover = n * [-1]
    last_cover = n * [-1]
    uncovered_count = 0
    max_covered_2_count = -1
    covered_2_count = -1
    covered_2 = (-1, -1)
    last_covered_2 = (-1, -1)
    for i in range(n):
        assert cover_size % 2 == 0
        if p[i] == i:
            if cover_size == 0:
                uncovered_count += 1
            elif cover_size == 2:
                covered_2_count += 1
            continue
        last_cover_size = cover_size
        last_covered_2 = covered_2
        if p[i] < i:
            delete_segment(i)
        else:
            add_segment(i)
        if p_inv[i] < i:
            delete_segment(p_inv[i])
        else:
            add_segment(p_inv[i])
        if cover_size == 2:
            s1 = current_cover
            s2 = next_cover[current_cover]
            covered_2 = (min(s1, s2), max(s1, s2))
        if last_cover_size == 0 and cover_size == 2:
            covered_2_count = 1
            last_covered_2 = covered_2
        elif last_cover_size == 2 and cover_size == 0:
            covered_2_count += 1
            max_covered_2_count = max(max_covered_2_count, covered_2_count)
            last_covered_2 = (-1, -1)
            covered_2_count = 0
        elif cover_size == 2 and covered_2 != last_covered_2:
            max_covered_2_count = max(max_covered_2_count, covered_2_count)
            last_covered_2 = covered_2
            covered_2_count = 0
    assert cover_size == 0
    print(uncovered_count + max_covered_2_count)

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

def f(u, v):
    return u << 20 ^ v
t = int(input())
ans = []
inf = pow(10, 9) + 1
for _ in range(t):
    n = int(input())
    p = [0] + list(map(int, input().split()))
    (l, r, s) = ([0] * (n + 2), [n + 1] * (n + 2), 0)
    for i in range(1, n + 1):
        l[i] = max(p[i], l[i - 1])
        if p[i] == l[i] == i:
            s += 1
    for i in range(n, 0, -1):
        r[i] = min(p[i], r[i + 1])
    if s == n:
        ans0 = n - 2
        ans.append(ans0)
        continue
    cnt = [0] * (n + 1)
    x = [0] * (n + 1)
    (ma1, ma2, j, k) = (-inf, -inf, 0, 0)
    u = set()
    for i in range(1, n + 1):
        if p[i] ^ i:
            u.add(f(i, p[i]))
    for i in range(1, n + 1):
        if p[i] == i and ma2 < i < ma1:
            (cnt[i], x[i]) = (1, j)
        if ma1 < p[i]:
            (ma1, ma2, j, k) = (p[i], ma1, i, j)
        elif ma2 < p[i]:
            (ma2, k) = (p[i], i)
    (mi1, mi2, j, k) = (inf, inf, 0, 0)
    for i in range(n, 0, -1):
        if p[i] == i and mi1 < i < mi2:
            u.add(f(x[i], j))
        if mi1 > p[i]:
            (mi1, mi2, j, k) = (p[i], mi1, i, j)
        elif mi2 > p[i]:
            (mi2, k) = (p[i], i)
    ans0 = s
    for i in range(1, n + 1):
        cnt[i] += cnt[i - 1]
    for k in u:
        (i, j) = (k >> 20, k & 1048575)
        (l0, r0) = (max(min(i, j), min(p[i], p[j])), min(max(i, j), max(p[i], p[j])) - 1)
        c = max(cnt[r0] - cnt[l0], 0)
        if i < j:
            if l[i - 1] == i - 1 and i == p[j]:
                c += 1
            if r[j + 1] == j + 1 and j == p[i]:
                c += 1
        else:
            if l[j - 1] == j - 1 and j == p[i]:
                c += 1
            if r[i + 1] == i + 1 and i == p[j]:
                c += 1
        ans0 = max(ans0, s + c)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))