题解：SP3544 BST - Binary Search Tree

youngsmart · 2024-11-03 08:50:49 · 题解

谁出的坑题！！！

这道题太毒了，我本来是以为这道题是模板，打个函数。

结果…… 50。

下面是正解

根据二叉搜索树的性质，思考一下可以发现我们每次只需要找到小于 a_i 的最大值和大于 a_i 的最小值。

但是暴力枚举就是 O( n^2 ) ，这不就超了？

我们机房的 dalao 推荐使用链表。

可是本蒟蒻不会，我就只能维护一个单调栈了。

代码来咯。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int n, a[N], id[N], l[N], r[N], s[N], d[N], top = 1;
long long ans;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), id[a[i]] = i;
    for (int i = 1; i <= n; i++)
    {
        while (id[i] < s[top] && top > 1) --top;
        l[i] = a[s[top]];
        s[++top] = id[i];
    }
    memset(s, 0, sizeof(s));
    top = 1;
    for (int i = n; i >= 1; i--)
    {
        while(id[i] < s[top] && top > 1) --top;
        r[i] = a[s[top]];
        s[++top] = id[i];
    }
    cout << 0 << endl;
    d[1] = -1;
    for (int i = 2; i <= n; i++)
    {
        ans += d[a[i]] = max(d[l[a[i]]], d[r[a[i]]]) + 1;
        cout << ans << endl;
    }
    return 0;
}

完结撒花。

壶关，见者有分。