rt

没学过线段树合并，所以不知道和题解有没有重复。

声明：只是单纯地分享一下考场思路，没有任何其他企图

对于一个节点 $fa$ 及其左儿子 $L$，右儿子 $R$，发现各自子树内的逆序对可以递归下去贪心，在 $fa$ 这里只需要考虑“跨过”$fa$ 的逆序对即可（也就是分治）。

考虑启发式分治，每次选 $siz$ 小的那个子树用树状数组计算逆序对数 $cnt$，将答案加上 $min( cnt , siz_L \times siz_R -cnt )$。

然后启发式合并，用 STL::vector 记录子树内的子节点；并将 $fa$ 继承大儿子的树状数组。

复杂度是丑陋的 $O(n \log^2n)$，但跑得飞快，平均30毫左右。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

inline int read(){
	int s=0;char c=getchar();
	while(c<48||c>57) c=getchar();
	while(c>=48&&c<=57) s=(s<<1)+(s<<3)+c-48,c=getchar();
	return s;
}

int num;

int n,top;
ll ans;
int L[500005],R[500005],siz[500005];
int v[500005],pos[500005];
vector<int> son[500005];

int init(){
	int p=++top,now=read();
	if(now){
		siz[p]=1,v[p]=now;
		pos[p]=p,son[p].push_back(v[p]);
		return p;
	}
	L[p]=init(),R[p]=init();
	if(siz[L[p]]<siz[R[p]]) swap(L[p],R[p]);
	siz[p]+=siz[L[p]],siz[p]+=siz[R[p]];
	return p;
}

int tre[200005];
int lowbit(int x){return x&-x;}
void add(int x,int y){while(x<=n) tre[x]+=y,x+=lowbit(x);}
int find(int x){int s=0;while(x>0) s+=tre[x],x-=lowbit(x);return s;}

void dfs(int x){
	int l=L[x],r=R[x];
	if(!l||!r){
		add(v[x],1);
		return;
	}
	
	ll cnt=0;int pl,pr;
	dfs(r),pr=pos[r]; for(int i=0;i<son[pr].size();i++) add(son[pr][i],-1);
	dfs(l),pl=pos[l]; for(int i=0;i<son[pr].size();i++) cnt+=siz[l]-find(son[pr][i]);
	
	ans+=min(cnt,(ll)siz[l]*siz[r]-cnt);
	for(int i=0;i<son[pr].size();i++) add(son[pr][i],1),
		son[pl].push_back(son[pr][i]);
	pos[x]=pl;
}

int main(){

	n=read();
	init();
	dfs(1);
	
	printf("%lld",ans);
	
	return 0;
}

代码也丑，希望对大家有帮助吧。

不过估计讨论版没人会理 吧 。

吃灰o(╥﹏╥)o