题目链接：BZOJ - 2212
题目分析
子树 x 内的逆序对个数为 ：x 左子树内的逆序对个数 + x 右子树内的逆序对个数 + 跨越 x 左子树与右子树的逆序对。
左右子树内部的逆序对与是否交换左右子树无关，是否交换左右子树取决于交换后 “跨越 x 左子树与右子树的逆序对” 是否会减小。
因此我们要求出两种情况下的逆序对数，使用线段树合并，对每个节点建一棵线段树，然后合并的同时就求出两种情况下的逆序对。
代码
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm> using namespace std; inline void Read(int &Num)
{
char c = getchar();
while (c < '0' || c > '9') c = getchar();
Num = c - '0'; c = getchar();
while (c >= '0' && c <= '9')
{
Num = Num * 10 + c - '0';
c = getchar();
}
} typedef long long LL; inline LL gmin(LL a, LL b) {return a < b ? a : b;} const int MaxN = 400000 + 5, MaxNode = 4000000 + 5; int n, IndexT, Index, RT;
int A[MaxN], Tree[MaxN][2], Root[MaxN], T[MaxNode], Son[MaxNode][2]; LL Ans0, Ans1, Ans; void Read_Tree(int &x)
{
x = ++IndexT;
Read(A[x]);
if (A[x] != 0) return;
Read_Tree(Tree[x][0]);
Read_Tree(Tree[x][1]);
} inline void Update(int x)
{
T[x] = T[Son[x][0]] + T[Son[x][1]];
} void Insert(int &x, int s, int t, int Pos)
{
if (x == 0) x = ++Index;
if (s == t)
{
T[x] = 1;
return;
}
int m = (s + t) >> 1;
if (Pos <= m) Insert(Son[x][0], s, m, Pos);
else Insert(Son[x][1], m + 1, t, Pos);
Update(x);
} int Merge(int x, int y)
{
if (!x) return y;
if (!y) return x;
Ans0 += (LL)T[Son[x][1]] * (LL)T[Son[y][0]];
Ans1 += (LL)T[Son[x][0]] * (LL)T[Son[y][1]];
Son[x][0] = Merge(Son[x][0], Son[y][0]);
Son[x][1] = Merge(Son[x][1], Son[y][1]);
Update(x);
return x;
} void Solve(int x)
{
if (A[x]) return;
Solve(Tree[x][0]); Solve(Tree[x][1]);
Ans0 = Ans1 = 0;
Root[x] = Merge(Root[Tree[x][0]], Root[Tree[x][1]]);
Ans += gmin(Ans0, Ans1);
} int main()
{
scanf("%d", &n);
Read_Tree(RT);
for (int i = 1; i <= IndexT; ++i)
if (A[i] != 0) Insert(Root[i], 1, n, A[i]);
Solve(RT);
cout << Ans << endl;
return 0;
}