记录编号	457357	评测结果	AAAAAAAAAA
题目名称	二叉查找树	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	0.550 s
提交时间	2017-10-07 18:50:49	内存使用	4.15 MiB

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=300001;
int n,t[maxn],l[maxn],r[maxn],u[maxn],v[maxn],cnt=1,i;
LL dep[maxn],ans;
int Main()
{
	freopen("bst.in","r",stdin);freopen("bst.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&t[i]);
		l[i]=i-1;
		r[i]=i+1;
	}
	for(i=n;i>1;i--)
	{
		int now=t[i];
		u[now]=l[now];
		v[now]=r[now];
		r[l[now]]=r[now];
		l[r[now]]=l[now];
	}
	for(i=1;i<=n;i++)
	{
		int now=t[i];
		if(u[now]>=1&&u[now]<=n)
			if(dep[now]<dep[u[now]]+1)
				dep[now]=dep[u[now]]+1;
		if(v[now]>=1&&v[now]<=n)
			if(dep[now]<dep[v[now]]+1)
				dep[now]=dep[v[now]]+1;
		ans+=dep[now];
		printf("%lld\n",ans);
	}
	return 0;
}
int main(){;}
int syy=Main();