Special Segments of Permutation (Codeforces 1156E)
Tags: Others, divide and conquer

You are given a permutation $$$p$$$ of $$$n$$$ integers $$$1$$$, $$$2$$$, ..., $$$n$$$ (a permutation is an array where each element from $$$1$$$ to $$$n$$$ occurs exactly once).Let's call some subsegment $$$p[l, r]$$$ of this permutation special if $$$p_l + p_r = \max \limits_{i = l}^{r} p_i$$$. Please calculate the number of special subsegments.

Input: The first line contains one integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$).The second line contains $$$n$$$ integers $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$ ($$$1 \le p_i \le n$$$). All these integers are pairwise distinct.

Output: Print the number of special subsegments of the given permutation.

Note: Special subsegments in the first example are $$$[1, 5]$$$ and $$$[1, 3]$$$.The only special subsegment in the second example is $$$[1, 3]$$$.

Sample Inputs:
5
3 4 1 5 2

3
1 3 2

Sample Outputs:
2

1

Solution (Python):
def Count_Segment(a, n):
    ans = 0
    upto = [False] * (n + 1)
    for i in range(1, n - 1):
        if a[i] > a[i - 1] and a[i] > a[i + 1]:
            curr = a[i]
            j = i - 1
            while j >= 0 and a[j] < curr:
                upto[a[j]] = curr
                j -= 1
            j = i + 1
            while j < n and a[j] < curr:
                if upto[curr - a[j]] == curr:
                    ans += 1
                j += 1
    return ans
n = int(input())
a = list(map(int, input().split()))
print(Count_Segment(a, n))

Solution (Python):
n = int(input())
ns = [int(x) for x in input().split()]
''
maxx = max(ns) + 10
lst = [None] * n
nxt = [None] * n
tmp = [(-1, maxx)]
mp = [False] * n
wh = [None] * (n + 1)
for i in range(n):
    c = ns[i]
    while tmp[-1][1] <= c:
        tmp.pop()
    lst[i] = tmp[-1][0]
    tmp.append((i, c))
tmp = [(n, maxx)]
for i in range(n):
    i = n - i - 1
    c = ns[i]
    while tmp[-1][1] <= c:
        tmp.pop()
    nxt[i] = tmp[-1][0]
    tmp.append((i, c))
lm = {}
for i in range(n):
    lm[lst[i] + 1, nxt[i] - 1] = ns[i]
for i in range(n):
    wh[ns[i]] = i

def check(i, m, lm):
    f = ns[m] - ns[i]
    f = wh[f]
    if lm[0] <= f <= lm[1]:
        return True
    return False
ans = 0
rec = [(0, n - 1)]

def get():
    if len(rec) == 0:
        return False
    (l, r) = rec.pop()
    if r - l + 1 <= 2:
        return True
    global ans
    x = lm[l, r]
    lc = wh[x]
    if lc < (l + r) // 2:
        for i in range(l, lc):
            c = ns[i]
            c = ns[lc] - c
            c = wh[c]
            if lc <= c <= r:
                ans += 1
    else:
        for i in range(lc + 1, r + 1):
            c = ns[i]
            c = ns[lc] - c
            c = wh[c]
            if l <= c <= lc:
                ans += 1
    rec.append((l, lc - 1))
    rec.append((lc + 1, r))
while len(rec) > 0:
    get()
print(ans)
quit()
get(0, n - 1)
print(ans)
quit()
x = n
while x >= 1:
    lc = wh[x]
    mp[lc] = True
    (l, r) = (lc - 1, lc + 1)
    while l > lst[lc] and (not mp[l]):
        l -= 1
    while r < nxt[lc] and (not mp[r]):
        r += 1
    if lc - l < r - lc:
        for i in range(l + 1, lc):
            if check(i, lc, (lc + 1, r - 1)):
                ans += 1
    else:
        for i in range(lc + 1, r):
            if check(i, lc, (l + 1, lc - 1)):
                ans += 1
    x -= 1
print(ans)

Solution (Python):
from collections import deque
from sys import stdin

def inv(perm):
    invp = [None] * len(perm)
    for (i, p) in enumerate(perm):
        invp[p] = i
    return invp

def main():
    n = int(stdin.readline())
    p = [int(x) - 1 for x in stdin.readline().split()]
    invp = inv(p)
    nexL = [None] * n
    nexR = [None] * n
    q = deque()
    for i in range(0, n):
        while q and p[q[-1]] <= p[i]:
            q.pop()
        nexL[i] = -1 if not q else q[-1]
        q.append(i)
    q.clear()
    for i in range(n - 1, -1, -1):
        while q and p[q[-1]] <= p[i]:
            q.pop()
        nexR[i] = n if not q else q[-1]
        q.append(i)
    res = 0
    for i in range(0, n):
        if i - nexL[i] < nexR[i] - i:
            for j in range(nexL[i] + 1, i):
                x = p[i] - p[j] - 1
                res += int(x >= 0 and i < invp[x] <= nexR[i])
        else:
            for j in range(i + 1, nexR[i]):
                x = p[i] - p[j] - 1
                res += int(x >= 0 and nexL[i] <= invp[x] < i)
    print(res)
main()