看到题解区清一色的用线段树在合并时维护信息，这里分享另一种类似于启发式合并，在树上直接计算答案的线段树合并做法。

首先，可将逆序对分为三种：左子树内部的逆序对、右子树内部的逆序对、跨左右子树的逆序对，从而可以递归求解。

容易发现，在非叶子节点处，无论左右子树是否交换，都不影响这棵子树内的元素集合。而对于逆序对而言，先算上左右子树内部的逆序对后，恰恰只需考虑左子树的元素集合与右子树的元素集合即可，左右子树内部的元素顺序并不重要。

因此考虑维护一棵权值线段树，以维护子树内的元素集合。在合并左右两棵子树的时候，可以枚举左子树的每个元素，再在右子树中用线段树查询小于此元素的元素数量，全部累加起来即可得到跨左右子树的逆序对数量。而交换左右子树的情况亦同理，最后取最小值即可。

然而这样做的时间复杂度是错误的，譬如构造一棵没有右儿子，一直向左延伸的树，这种做法就被卡成 $O(n^2)$ 了，因此考虑优化。

注意到某棵子树内的元素数量对其线段树的时间复杂度并无影响，因为权值线段树单次查询的时间复杂度始终为 $O(\log n)$，所以只要使枚举的元素尽可能少即可。具体来说就是在计算逆序对个数前比较左右子树元素数量，然后只枚举元素少的那棵子树内的元素，用线段树快速计算另一棵子树。

这样做的话，对于每一个节点，枚举的元素数量一定小于或等于子树内总元素数量的一半，因此枚举的时间类似于启发式合并，在树上合并信息的复杂度最多为 $O(n\log n)$，再算上线段树，总的时间复杂度为 $O(n\log^2 n)$。

代码如下，具体看注释：

#include<bits/stdc++.h>
using namespace std;
int n,nl,pl,p[200010],lc[400010],rc[400010],ll[400010],rr[400010],rt[400010];
int trl,ls[4000010],rs[4000010],tree[4000010];
long long sum;
int init(){
	nl+=1;
	int x=nl,px;
	scanf("%d",&px);
	if(px!=0)
	{
		pl+=1;
		p[pl]=px;
		ll[x]=pl;
		rr[x]=pl;
		return x;
	}
	lc[x]=init();
	rc[x]=init();
	ll[x]=ll[lc[x]];
	rr[x]=rr[rc[x]];
	//维护子树内的元素在整体元素序列中的区间 
	return x;
}
int node(int &x){
	if(x==0)
	{
		trl+=1;
		x=trl;
	}
	return x;
}
void change(int l,int r,int x,int k,int v){
	if(l==r)
	{
		tree[x]+=v;
		return;
	}
	int mid=(l+r)>>1;
	if(k<=mid)change(l,mid,node(ls[x]),k,v);
	else change(mid+1,r,node(rs[x]),k,v);
	tree[x]=tree[ls[x]]+tree[rs[x]];
}
int merge(int l,int r,int x,int y){
	if(x==0||y==0)return x+y;
	if(l==r)
	{
		tree[x]+=tree[y];
		return x;
	}
	int mid=(l+r)>>1;
	ls[x]=merge(l,mid,ls[x],ls[y]);
	rs[x]=merge(mid+1,r,rs[x],rs[y]);
	tree[x]=tree[ls[x]]+tree[rs[x]];
	return x;
}
int ask(int l,int r,int x,int ll,int rr){
	if(l>rr||r<ll||ll>rr||x==0)return 0;
	if(l>=ll&&r<=rr)return tree[x];
	int mid=(l+r)>>1;
	return ask(l,mid,ls[x],ll,rr)+ask(mid+1,r,rs[x],ll,rr);
}
void dfs(int x){
	if(lc[x]+rc[x]==0)
	{
		change(1,n,node(rt[x]),p[ll[x]],1);
		return;
	}
	dfs(lc[x]);
	dfs(rc[x]);
	if(rr[lc[x]]-ll[lc[x]]>rr[rc[x]]-ll[rc[x]])swap(lc[x],rc[x]);
	//使左子树始终为元素数量较小的子树 
	long long sum1=0,sum2=0;
	for(int i=ll[lc[x]];i<=rr[lc[x]];i++)
		sum1+=ask(1,n,rt[rc[x]],1,p[i]-1);
	//不交换左右子树 
	for(int i=ll[lc[x]];i<=rr[lc[x]];i++)
		sum2+=ask(1,n,rt[rc[x]],p[i]+1,n);
	//交换左右子树 
	sum+=min(sum1,sum2);
	rt[x]=merge(1,n,rt[lc[x]],rt[rc[x]]);
}
int main(){
	scanf("%d",&n);
	init();
	dfs(1);
	printf("%lld",sum);
	return 0;
}