很有意思的一道题呀，考试时写挂了
显然一个数插入时要添加的次数等于他插入到数的深度
根据BST的性质
当我们插入了一颗数后按他的Insert函数操作
对于这个数他一定在他前驱的右儿子中也一定在他后继的左儿子中（没有重复数字且1-N）
由于他的插入不保证平衡，显然插入的数一定在前驱和后继的下一层
且在深度更深的那个的下一层
（感觉我的证明有误）
所以我们只需要关注他的前驱和后继就行了
直接一个set就行了
还可以优化
考虑[NOI2004]郁闷的出纳员的套路
当我们只关注前驱和后继时可以用链表来实现线性的做法
由于末尾状态一定且删除只会对两个数造成影响可以O（1）计算
考虑倒序处理用链表维护当前序列他指向的前驱和后继
代码如下
#include<bits/stdc++.h> using namespace std; const int MAXN = 300000 + 10; inline int read() { int f=1,x=0; char ch; do { ch=getchar(); if(ch==‘-‘) f=-1; }while(ch<‘0‘||ch>‘9‘); do { x=(x<<3)+(x<<1)+ch-‘0‘; ch=getchar(); }while(ch>=‘0‘&&ch<=‘9‘); return f*x; } int n; int a[MAXN]; int l[MAXN],r[MAXN],pre[MAXN],nex[MAXN]; long long dep[MAXN],ans; int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) { l[i]=i-1;r[i]=i+1; } l[1]=0;r[n]=0; cout<<0<<endl; for(int i=n;i>=1;i--) { pre[a[i]]=l[a[i]]; nex[a[i]]=r[a[i]]; r[l[a[i]]]=r[a[i]]; l[r[a[i]]]=l[a[i]]; } for(int i=2;i<=n;i++) { dep[a[i]]=max(dep[pre[a[i]]],dep[nex[a[i]]])+1; ans+=dep[a[i]]; cout<<ans<<endl; } }
SP3544 BST - Binary Search Tree
原文：https://www.cnblogs.com/wlzs1432/p/11286150.html