题目链接：Codeforces 1156E

你有一个长度为 $n$ 的排列 $p$，假如 $p_l + p_r = \max_{i = l} ^ r p_i$，那么我们称子段 $p[l, r]$ 是特殊的。请你找出特殊的子段数量。

数据范围：$3 \le n \le 2 \times 10 ^ 5$。

Solution

遇到区间最大值一类的问题，第一反应就是通过单调栈求出第 $i$ 个元素可以成为最大值的区间 $[l_i, r_i]$。

对于第 $i$ 个元素，我们枚举 $[l_i, i]$ 区间内的元素作为 $p_l$，得到对应的另一个元素 $p_r = p_i - p_l$，如果 $p_r$ 在排列中出现的位置 $\in [i, r_i]$ 那么对答案有 $1$ 的贡献。这样我们就得到了一个 $\mathcal O(n ^ 2)$ 的解法。

考虑对上述做法做一个看似无用的优化：每次枚举长度较短的一侧。考虑这样对于复杂度的影响：考虑对这个排列建树，每次把区间最大值拿出来，左侧子区间作为左子树，右侧子区间作为右子树。对于每个节点，复杂度为 $\mathcal O(\min(size($\text{lson}), size($\text{rson})))$。这就是启发式合并的复杂度。因此这种优化可以将复杂度大幅降低为 $\mathcal O(n \log n)$。

时间复杂度：$\mathcal O(n \log n)$。

Code

#include <cstdio>

const int N = 2e5 + 5;

int n, a[N], pos[N], stk[N], l[N], r[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pos[a[i]] = i;
    }
    int top;
    stk[top = 0] = 0;
    for (int i = 1; i <= n; i++) {
        for (; top && a[stk[top]] < a[i]; top--);
        l[i] = stk[top] + 1;
        stk[++top] = i;
    }
    stk[top = 0] = n + 1;
    for (int i = n; i >= 1; i--) {
        for (; top && a[stk[top]] < a[i]; top--);
        r[i] = stk[top] - 1;
        stk[++top] = i;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i - l[i] < r[i] - i) {
            for (int j = l[i]; j <= i; j++) {
                int t = pos[a[i] - a[j]];
                if (i <= t && t <= r[i]) ans++;
            }
        } else {
            for (int j = i; j <= r[i]; j++) {
                int t = pos[a[i] - a[j]];
                if (l[i] <= t && t <= i) ans++;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}