一个初始为空的二叉搜索树T，以及1到N的一个排列P: {a1, a2, ..., aN}。我们向这个二叉搜索树T添加这些数，从a1开始, 接下来是 a2, ...， 以aN结束。在每一个添加操作后，输出T上每对节点之间的距离之和。
例如：4 7 3 1 8 2 6 5。最终的二叉树为：
4
/ \
3 7
/ / \
1 6 8
\ /
2 5
节点两两之间的距离和 = 6+5+5+4+3+2+1+5+4+4+3+2+1+4+3+3+2+1+3+2+2+1+2+1+1+2+1+3 = 76
Input
第1行：1个数N。(1 <= N <= 100000)
第2 - N + 1行：每行1个数，对应排列的元素。(1 <= ai <= N)
Output
输出共N行，每行1个数，对应添加当前元素后，每对节点之间的距离之和。
用set维护一下空的左右孩子位置和已插入的点可以O(nlogn)建树
然后就每加入 √(n) 个点重新树形dp一次，每加入一个点时和之前已加入但未dp的点间求距离，并计算和已dp的点对答案的贡献。
总复杂度O(n√(n)logn)
读入优化t了4个点，读入+输出优化t了1个点，fread+fwrite才a。。
#include<stdio.h>
#include<set>
#include<cmath>
const int N=;
char buf[],*ptr=buf,rbuf[],*rptr=rbuf-;
inline int _(){
int x=,c=*++rptr;
while(c<)c=*++rptr;
while(c>)x=x*+c-,c=*++rptr;
return x;
}
inline void _(long long x){
static int stk[],stp=;
if(!x)stk[stp++]=;
while(x)stk[stp++]=x%,x/=;
while(stp)*ptr++=stk[--stp]+;
*ptr++=;
}
int n,pv=;
std::set<int>le,re,in;
int ch[N][],xs[N],dep[N],fa[N],sz[N],pf[N],top[N];
long long F1[N],F2[N],ans=,ANS[N];
int _sz[N],h[N],tp[N];
inline int dis(int x,int y){
int a=top[x],b=top[y],s=dep[x]+dep[y];
while(a!=b){
if(dep[a]<dep[b])y=fa[b],b=top[y];
else x=fa[a],a=top[x];
}
s-=dep[dep[x]<dep[y]?x:y]<<;
return s;
}
void rebuild(){
ans=;
for(int i=pv-;~i;--i){
int w=xs[i],lc=ch[w][],rc=ch[w][];
h[w]=;
_sz[w]=+_sz[lc]+_sz[rc];
F1[w]=_sz[w]-+F1[lc]+F1[rc];
}
for(int i=;i<pv;++i){
int w=xs[i],lc=ch[w][],rc=ch[w][],s=_sz[rc]-_sz[lc];
F2[lc]=pv+s+F2[w]+F1[rc];
F2[rc]=pv-s+F2[w]+F1[lc];
F1[w]+=F2[w];
ans+=F1[w];
}
ans>>=;
}
int main(){
rbuf[fread(rbuf,,,stdin)]=;
n=_();
xs[]=_();
le.insert(xs[]);
re.insert(xs[]);
in.insert(xs[]);
for(int i=;i<n;++i){
int x=xs[i]=_();
in.insert(x);
auto it=le.upper_bound(x);
if(it!=le.end()){
auto it2=in.upper_bound(x);
if(it2!=in.end()&&*it2==*it){
ch[fa[x]=*it][]=x;
le.erase(it);
le.insert(x),re.insert(x);
continue;
}
}
it=re.upper_bound(x);
--it;
ch[fa[x]=*it][]=x;
re.erase(it);
le.insert(x),re.insert(x);
}
for(int i=;i<n;++i){
int w=xs[i];
dep[w]=dep[fa[w]]+;
}
for(int i=n-;~i;--i){
int w=xs[i];
int sl=sz[ch[w][]],sr=sz[ch[w][]];
sz[w]=+sl+sr;
pf[w]=ch[w][sl<sr];
}
for(int i=;i<n;i++){
int w=xs[i];
if(!top[w])for(int u=w;u;u=pf[u])top[u]=w;
}
int B=std::sqrt(n)/1.2+;
for(int i=;i<n;++i){
int w=xs[i],f=fa[w];
tp[w]=h[f]?tp[f]:f;
h[w]=h[f]+;
ans+=h[w]*pv+F1[tp[w]];
for(int j=pv;j<i;j++)ans+=dis(w,xs[j]);
ANS[i]=ans;
if(i%B==B-){
pv=i+;
rebuild();
}
}
for(int i=;i<n;++i)_(ANS[i]);
fwrite(buf,,ptr-buf,stdout);
return ;
}