题解：SP3544 BST - Binary Search Tree

题目大意

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

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

思路

暴力模拟肯定会超时，根据二叉搜索树的性质：

设第 i 个节点的权值 x，则其左子树中的权值都小于 x，右子树中的权值都大于 x。

思考一下可以发现我们每次只需要找到小于第 i 个数的最大值，和大于第 i 个数的最小值。这时候，这两个数一定是编号为 i 的左右孩子。

因为单调栈刚好可以处理这种问题（‌找到某个数的左右边比它大/小的最近的数‌），所以可以考虑用它解决这道题。又由于 1\le a_{i}\le n，a_{i} 互不相同，所以数字可以从 1 开始模拟到 n，找到第 i 个数左边比它小的数的最大值，再从 n 开始模拟到 1，找到第 i 个数右边比它大的最小值。

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

干完这一切之后，发现计数器跟深度（从这个节点到根节点的最长路径）有关系，所以只需处理它的深度并输出即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int i,top,n,stck[maxn],id[maxn],a[maxn],L[maxn],R[maxn],dep[maxn];
long long ans=0;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i],id[a[i]]=i; //id[i]:数i的位置
    a[0]=id[0]=top=stck[top]=0;
    for(i=n;i>=1;i--){//按数值从大到小处理，位置入栈，
        while(top>=0){
            if(stck[top]>id[i]) top--;
            else break;
        }
        R[i]=a[stck[top]];
        stck[++top]=id[i];
    }
    top=0;
    dep[0]=-1;
    for(i=1;i<=n;i++){//按数值从小到大处理，位置入栈
        while(top>=0){
            if(stck[top]>id[i]) top--;
            else break;
        }
        L[i]=a[stck[top]];
        stck[++top]=id[i];
    }//栈里的位置值从小到大
    for(i=1; i<=n; i++) {
        dep[a[i]]=1+max(dep[L[a[i]]],dep[R[a[i]]]);
        ans=ans+dep[a[i]];
        cout<<ans<<"\n";
    }
    return 0;
}