记录编号	457756	评测结果	AAAAAAAAAAAAA
题目名称	二叉查找树	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.519 s
提交时间	2017-10-09 11:47:58	内存使用	6.54 MiB

#include<cstdio>
const int N=3e5+10;
int n,ran[N],v[N],fa[N],dep[N];
int main()
{
	freopen("bst.in","r",stdin);
	freopen("bst.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&v[i]),ran[v[i]]=i;
	for (int i=1;i<=n;i++){
		int last=0,f=i-1;
		while (ran[f]>ran[i]) last=f,f=fa[f];
		fa[i]=f;
		if (last) fa[last]=i;
	}
	dep[0]=-1;
	long long sum=0;
	for (int i=1;i<=n;i++){
		dep[v[i]]=dep[fa[v[i]]]+1;
		sum+=dep[v[i]];
		printf("%lld\n",sum);
	}
	return 0;
}