Siyuan

「Codeforces 1156E」Special Segments of Permutation
「Codeforces 1156E」Special Segments of Permutation
扫描右侧二维码阅读全文
20
2019/05

「Codeforces 1156E」Special Segments of Permutation

题目链接: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;
}
最后修改:2019 年 06 月 01 日 05 : 54 PM

发表评论