一个初始为空的二叉搜索树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个数，对应添加当前元素后，每对节点之间的距离之和。
Input示例
8 4 7 3 1 8 2 6 5
Output示例
0 1 4 10 20 35 52 76
set+动态点分治~
我们用一个set记录所有点，加入点时，寻找它最大的小于它的节点和最小的大于它的节点，看它们有没有右/左子节点，没有就加上，可以快速建图。
——这里和宠物收养所是一样的。
然后就是动态点分治辣！
#include<cstdio>
#include<cstring>
#include<iostream>
#include<set>
using namespace std;
#define ll long longconst int inf=999999999;int n,x,y,z,a[100001],f[100001],dep[100001],anc[100001][22],siz[100001];
int fi[100005],w[200010],ne[200010],cnt,tot,root,mx[100001],dis[100001][22];
ll ans1[100001],ans2[100001],ans,num[100001];
bool c[100001][2],vis[100001];set<int> s;
set<int>::iterator le,ri;int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;
}void add(int u,int v)
{w[++cnt]=v;ne[cnt]=fi[u];fi[u]=cnt;w[++cnt]=u;ne[cnt]=fi[v];fi[v]=cnt;
}void findroot(int u,int fa)
{siz[u]=1;mx[u]=0;for(int i=fi[u];i;i=ne[i])if(w[i]!=fa && !vis[w[i]]){findroot(w[i],u);siz[u]+=siz[w[i]];mx[u]=max(mx[u],siz[w[i]]);}mx[u]=max(mx[u],tot-siz[u]);if(mx[u]<mx[root]) root=u;
}void finddep(int u,int fa,int ancc,int diss)
{dep[u]++;anc[u][dep[u]]=ancc;dis[u][dep[u]]=diss;for(int i=fi[u];i;i=ne[i])if(w[i]!=fa && !vis[w[i]]) finddep(w[i],u,ancc,diss+1);
}void dfs(int u)
{mx[root=0]=inf;findroot(u,0);finddep(root,root,root,0);vis[root]=1;dep[root]--;for(int i=fi[root];i;i=ne[i])if(!vis[w[i]]){findroot(w[i],0);tot=siz[w[i]];dfs(w[i]);}
}void sol(int u)
{ans+=ans1[u];for(int i=dep[u];i>1;i--){ans+=ans1[anc[u][i-1]]-ans2[anc[u][i]];ans+=dis[u][i-1]*(num[anc[u][i-1]]-num[anc[u][i]]);}num[u]++;for(int i=dep[u];i>1;i--){ans1[anc[u][i-1]]+=dis[u][i-1];ans2[anc[u][i]]+=dis[u][i-1];num[anc[u][i-1]]++;}printf("%lld\n",ans);
}int main()
{n=read();s.insert(-inf);s.insert(inf);a[1]=x=read();s.insert(x);for(int i=2;i<=n;i++){a[i]=x=read();ri=s.lower_bound(x);le=ri;le--;s.insert(x);if(*ri!=inf && !c[*ri][0]) c[*ri][0]=1,add(*ri,x);else c[*le][1]=1,add(*le,x);}tot=n;dfs(1);for(int i=1;i<=n;i++) anc[i][++dep[i]]=i;for(int i=1;i<=n;i++) sol(a[i]);return 0;
}