题解 P6412 [COCI2008-2009#3] BST

kkxacj · 2023-01-07 16:54:10 · 题解

upd: 增加文章可读性。

题目传送门

题意

现在有一个 1\sim n 的排列 a，将序列中的元素依次放进一个 BST 里，求 BST 中插入函数的执行次数。

注意：第一个数已经作为 BST 的根。

思路

暴力模拟肯定会超时，根据二叉搜索树的性质，思考一下可以发现我们每次只需要找到小于第 i 个数的最大值和大于第 i 个数的最小值。

所以可以考虑用单调栈解决这道题，又由于 1\le a_i\le n，a_i 互不相同，所以数字可以从 1 开始模拟到 n,找到第 i 个数左边比它小的数的最大值,再从 n 开始模拟到 1,找到第 i 个数右边比它大的最小值。

注意：由于找第 i 个数右边比它大的最小值不能是还没有输入的，所以我们应该找第 i 个数左边比它大的最小值。

干完这一切之后，只需计算它的深度即可。

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 300005;
int n,k,dep[maxn],l[maxn],r[maxn],a[maxn],x[maxn],d[maxn],cnt = 1;
long long ans;
int main()
{
//   freopen(".in","r",stdin);
//   freopen(".out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++) 
    {
        scanf("%d",&x[i]);
        a[x[i]] = i; 
    } 
    for(int i = 1;i <= n;i++)
    {
        while(a[i] < d[cnt] && cnt > 1) cnt--;
        l[i] = x[d[cnt]];
        d[++cnt] = a[i];
    }
    int cnt = 1;
    for(int i = n;i >= 1;i--)
    {
        while(a[i] < d[cnt] && cnt > 1) cnt--;
        r[i] = x[d[cnt]];
        d[++cnt] = a[i];
    }
    cout << 0 << endl;
    for(int i = 2;i <= n;i++) 
    {
        dep[x[i]] = 1 + max(dep[l[x[i]]],dep[r[x[i]]]);
        ans += dep[x[i]];
        printf("%lld\n",ans);
    }
    return 0;
}