Description：

给出一个 $n$ 的排列，按照这个排列的顺序加数建立一棵二叉查找树，每插入一个点询问树上所有点对距离之和。

$1\le n \le 10^5$

Solution：

发现一个点一定是他的前驱的右儿子和他的后继的左儿子，且同一时刻一定只有一个满足，于是用一个 $set$ 查询前驱后继然后直接连边即可，这样建树是 $O(n\log n)$ 的。树建出来之后问题就是动态维护树上所有点对距离和，动态点分治，维护一个点分子树到根的距离和和点分子树大小即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<set>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

int a[MAXN];

set<int> s;

#define INF 0x3f3f3f3f

int pre(int x)

{

	s.insert(x);

	set<int>::iterator it = s.find(x);

	int res;

	if(it == s.begin())res = INF;

	else{--it;res = *it;}

	s.erase(x);

	return res;

}

int nxt(int x)

{

	s.insert(x);

	set<int>::iterator it = s.find(x);

	int res;

	if(it == s.end())res = INF;

	else{++it;res = *it;}

	s.erase(x);

	return res;

}

int lc[MAXN],rc[MAXN];

int size[MAXN],d[MAXN],root,sum;

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int fa[MAXN],siz[MAXN],dep[MAXN],top[MAXN],son[MAXN];

void dfs1(int k,int depth)

{

	dep[k] = depth;siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

int dis(int a,int b){return dep[a] + dep[b] - 2 * dep[LCA(a,b)];}

bool v[MAXN];

void getroot(int k,int fa)

{

	size[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to] || e[i].to == fa)continue;

		getroot(e[i].to,k);

		size[k] += size[e[i].to];

		if(size[e[i].to] > d[k])

		{

			d[k] = size[e[i].to];

		}

	}

	d[k] = max(d[k],sum - size[k]);

	if(d[k] < d[root])root = k;

	return;

}

int anc[MAXN];

void divide(int k)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!v[e[i].to])

		{

			root = 0;sum = size[e[i].to];

			getroot(e[i].to,0);

			anc[root] = k;

			divide(root);

		}

	}

	return;

}

typedef long long ll;

ll sumv[MAXN],tofa[MAXN],tot[MAXN];

void modify(int k)

{

	++tot[k];

	for(int i = k;anc[i] != 0;i = anc[i])

	{

		ll d = dis(k,anc[i]);

		++tot[anc[i]];

		tofa[i] += d;

		sumv[anc[i]] += d;

	}

	return;

}

ll query(int k)

{

	ll res = sumv[k];

	for(int i = k;anc[i] != 0;i = anc[i])

	{

		ll d = dis(k,anc[i]);

		res += d * (tot[anc[i]] - tot[i]) + sumv[anc[i]] - tofa[i];

	}

	return res;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	s.insert(a[1]);

	for(int i = 2;i <= n;++i)

	{

		int pr = pre(a[i]),nx = nxt(a[i]);

		if(pr != INF && rc[pr] == 0)rc[pr] = a[i];

		else lc[nx] = a[i];

		s.insert(a[i]);

	}

	for(int i = 1;i <= n;++i)

	{

		if(lc[i] != 0)add(i,lc[i]);

		if(rc[i] != 0)add(i,rc[i]);

	}

	dfs1(1,1);dfs2(1,1);

	sum = n;root = 0;d[0] = INF;

	getroot(1,0);

	divide(root);

	ll ans = 0;

	for(int i = 1;i <= n;++i)

	{

		modify(a[i]);

		ans += query(a[i]);

		printf("%lld\n",ans);

	}

	return 0;

}