记录编号	457789	评测结果	AAAAAAAAAAAAA
题目名称	二叉查找树	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	1.255 s
提交时间	2017-10-09 15:32:55	内存使用	6.04 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring> 
#define ll long long
using namespace std;
/*
	权值线段树；
	插入某个点p
	查询这个这个点的先驱和后继；
	取深度大的； 
*/
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int maxn=3e5+10;
int n;
int dep[maxn];
int sum[maxn<<2];
inline void change(int o,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr){
		sum[o]=1;
		return ;
	}
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	if(m>=nl)change(ls,l,m,nl,nr);
	if(m<nr)change(rs,m+1,r,nl,nr);
	sum[o]=sum[ls]+sum[rs];
}
inline int findsum(int o,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr)return sum[o];
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	int ans=0;
	if(m>=nl)ans+=findsum(ls,l,m,nl,nr);
	if(m<nr)ans+=findsum(rs,m+1,r,nl,nr);
	return ans;
}
inline int kth(int o,int l,int r,int k){
	if(l==r)return l;
	int m=(l+r)>>1,ls=o<<1,rs=ls|1;
	if(k<=sum[ls])return kth(ls,l,m,k);
	else return kth(rs,m+1,r,k-sum[ls]); 
}
ll ans;
int main(){
	freopen("bst.in","r",stdin);
	freopen("bst.out","w",stdout);
	n=read();
	int fir=read();
	change(1,1,n,fir,fir);
	puts("0");
	for(int i=2;i<=n;i++){
		int p=read(),qian,hou;
		int lsum=findsum(1,1,n,1,p);
		int tsum=sum[1];
		//cout<<"总"<<lsum<<" "<<tsum<<endl;
		if(lsum==0){//无前驱； 
			hou=kth(1,1,n,1);
			ans+=(ll)(dep[hou]+1);
			dep[p]=dep[hou]+1;
			//cout<<hou<<" "<<p<<endl;
			change(1,1,n,p,p);
			printf("%lld\n",ans);
			continue;
		}
		if(lsum==tsum){//无后继 
			qian=kth(1,1,n,lsum);
			ans+=(ll)(dep[qian]+1);
			dep[p]=dep[qian]+1;
			//cout<<qian<<" "<<p<<endl;
			change(1,1,n,p,p);
			printf("%lld\n",ans);
			continue;
		}
		//cout<<qian<<" "<<hou<<" "<<p<<endl;
		qian=kth(1,1,n,lsum);
		hou=kth(1,1,n,lsum+1);
		int jia=max(dep[qian],dep[hou])+1;
		ans+=(ll)jia;
		dep[p]=jia;
		change(1,1,n,p,p);
		printf("%lld\n",ans);
	}
	return 0;
}