Description：

给一棵二叉树，每次可以交换两个儿子节点，每个儿子节点的编号是一个 $1\sim n$ 的排列，问怎样交换使得整棵树的逆序对数最小。

$1\le n \le 200000$

Solution：

总逆序对数 $=$ 子树逆序对数 $+$ 子树间逆序对数，这说明我们可以递归地处理这颗二叉树。

我们每个点维护一棵权值线段树，这样就可以计算出两个子节点之间的逆序对数(类似树状数组求逆序对)，取交换和不交换中较小的，然后把两个子节点的线段树合并起来作为父节点的线段树，发现上面的计算过程其实可以在线段树合并时一并计算，因为线段树合并是一个类似的递归过程。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 200010

int ls[MAXN << 1],rs[MAXN << 1];

int tot = 0;

struct node

{

	int lc,rc;

	int tot;

	node(){tot = 0;}

}t[MAXN * 30];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN << 1];

#define mid ((l + r) >> 1)

void insert(int &rt,int p,int l,int r)

{

	if(rt == 0)rt = newnode();

	++t[rt].tot;

	if(l == r)return;

	if(p <= mid)insert(t[rt].lc,p,l,mid);

	else insert(t[rt].rc,p,mid + 1,r);

	return;

}

void read(int k)

{

	int w;

	scanf("%d",&w);

	if(w != 0)insert(root[k],w,1,n);

	else

	{

		read(ls[k] = ++tot);

		read(rs[k] = ++tot);

	}

	return;

}

long long tmp1,tmp2;

int merge(int x,int y)

{

	if(!x)return y;if(!y)return x;

	t[x].tot += t[y].tot;

	tmp1 += (long long)t[t[x].lc].tot * t[t[y].rc].tot;

	tmp2 += (long long)t[t[y].lc].tot * t[t[x].rc].tot;

	t[x].lc = merge(t[x].lc,t[y].lc);

	t[x].rc = merge(t[x].rc,t[y].rc);

	return x;

}

long long ans = 0;

void dfs(int k)

{

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

	dfs(ls[k]);dfs(rs[k]);

	tmp1 = tmp2 = 0;

	root[k] = merge(root[ls[k]],root[rs[k]]);

	ans += min(tmp1,tmp2);

	return;

}

int main()

{

	scanf("%d",&n);

	read(++tot);

	dfs(1);

	cout << ans << endl;

	return 0;

}