CF1156E Special Segments of Permutation

link

标签

笛卡尔树 + 启发式 + 单调队列

难度

思维难度 : 三星

代码难度 ：两星

思路

问有多少个区间满足 $p[l]+p[r]=\max_{i=l}^{r}{p[i]}$ 。
很显然可以想到要对 $max$ 求贡献，用单调栈对每个点求出不包含比它大的数的最大区间。因为枚举左边和枚举右边贡献是等价的，所以从这个点向更短的那一边枚举。看起来很暴力，但是复杂度是 $O(n\lg n)$ 的. 原因如下。

其实这相当于对序列建了一棵笛卡尔树，枚举更小的子树。这样的复杂度显然是 $O(n \lg n)$ 的。这里只不过是没有把笛卡尔树显示的建出来.

Code

#include <iostream>
#include <stack>
#include <cstring>
#define ll long long

using namespace std;

const int N = 4e5 + 10;
int l[N], r[N], n;
int a[N], pos[N];
int q[N], tot;

signed main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        pos[a[i]] = i;
    }
    for (int i = 1; i <= n; ++i) {
        while (tot && a[q[tot]] < a[i]) {
            r[q[tot]] = i - 1;
            --tot;
        }
        q[++tot] = i;
    }
    while (tot) {
        r[q[tot]] = n;
        --tot;
    }
    for (int i = n; i; --i) {
        while (tot && a[q[tot]] < a[i]) {
            l[q[tot]] = i + 1;
            --tot;
        }
        q[++tot] = i;
    }
    while (tot) {
        l[q[tot]] = 1;
        --tot;
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (i - l[i] > r[i] - i) {
            for (int j = i + 1; j <= r[i]; ++j) {
                if (pos[a[i] - a[j]] < i && pos[a[i] - a[j]] >= l[i]) ++ans;
            }
        }
        else {
            for (int j = i - 1; j >= l[i]; --j) {
                if (pos[a[i] - a[j]] > i && pos[a[i] - a[j]] <= r[i]) ++ans;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

总结

1. 遇到和区间的 $max$ 有关的求数量算贡献的题，要考虑笛卡尔树，单调 栈。
2. 借助笛卡尔树可以在树上用启发式来优化复杂度