出处:http://blog.csdn.net/enjoying_science/article/details/44114035
（有难度，以后回来填坑）
阅读代码中：
#include<stdio.h>
#include<iostream>
using namespace std;
#define ForD(i,n) for(int i=n;i;i--)
#define F (100000007)
#define MAXN (2*200000+10)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} int n,root=;/*n->叶子结点数,root->根序号？*/
struct node
{
int fa; /*父结点的下标*/
int ch[]; /*0->左树下标 1->右树下标*/
int size; /*size->当前结点含有的有效结点数*/
int c; /*当前结点的数值*/
node():size(),c(){ch[]=ch[]=fa=;} /*初始化为0*/
}a[MAXN]; /*树形数组->纪录各叶结点的数值*/ void update(int x)/*更新叶结点个数*/
{
a[x].size=a[a[x].ch[]].size+a[a[x].ch[]].size+(a[x].c>);
}
int tail=;
void pushdown(int x)/*将叶结点的父结点指向当前结点*/
{
a[a[x].ch[]].fa=a[a[x].ch[]].fa=x;
} /*创建树*/
void build(int &x)
{
if (!x) x=++tail;
scanf("%d",&a[x].c);
if (a[x].c==)
{
build(a[x].ch[]);/*创建左子树*/
build(a[x].ch[]);/*创建右子树*/
update(x);pushdown(x);/*更新当前结点的有效叶结点个数，以及父结点指向*/
}else a[x].size=;
} void rotate(int x)/*旋转*/
{
int y=a[x].fa,z=a[y].fa;
bool p=a[y].ch[]==x;
if (z) /*有爷爷*/
{
if (a[z].ch[]==y) /*未旋转*/
a[z].ch[]=x;/*将子树提拔为父树(升序)*/
else
a[z].ch[]=x; /*还原状态*/
}
a[x].fa=z,a[y].fa=x;/*当前结点与父结点交换(父结点指向)*/
if (a[x].ch[p]) /*原子树是否有右树(隔代转移)*/
a[a[x].ch[p]].fa=y;
a[y].ch[p^]=a[x].ch[p];
a[x].ch[p]=y; /*父树移至子树的右端(右树)*/
update(y); /*更新旋转后，子树的结点的有效结点数*/
} void splay(int x)
{
while (a[x].fa)/*不为根结点*/
{
int y=a[x].fa,z=a[y].fa;
if (z) /*有爷爷*/
if ((a[y].ch[]==x)^(a[z].ch[]==y)) rotate(x);/*旋转*/
else rotate(y);
rotate(x);
}
update(x);
}
void ins(long long &tot,int x,int y)
{
a[x].size++; /*插入+1*/
if (a[y].c<=a[x].c) /*是逆序对*/
{
if (a[x].ch[]) /*左树有子*/
ins(tot,a[x].ch[],y);
else /*左树无子*/
a[y].fa=x,splay(a[x].ch[]=y);/*右数插入到左树子*/
}
else
{
tot+=a[a[x].ch[]].size+(a[x].c>);
if (a[x].ch[]) ins(tot,a[x].ch[],y);
else a[y].fa=x,splay(a[x].ch[]=y);
}
} int q[MAXN],size; void clac(int x,int y)
{
if (a[y].ch[]) clac(x,a[y].ch[]);
if (a[y].c) q[++size]=y;
if (a[y].ch[]) clac(x,a[y].ch[]);
} long long merge(bool &lor,int z)/*分治*/
{
int x=a[z].ch[],y=a[z].ch[];
if (a[x].size<a[y].size) /*判断叶结点多的往前调(平衡树?)*/
swap(x,y); a[x].fa=;a[y].fa=;q[]=y;
size=;clac(x,y);
long long tot=; /*最少逆序对*/
ForD(i,size) /*循环（子结点数）次*/
{
int now=q[i];
a[now].ch[]=a[now].ch[]=a[now].fa=;
a[now].size=;
ins(tot,x,now);
x=now;
}
a[x].fa=z;
a[z].ch[]=,a[z].ch[]=x;
return tot;
} long long qur(int &x)
{
if (a[x].c) return ;/*若根结点没有叶结点，则逆序对为0*/
else
{
long long lson=a[a[x].ch[]].size,rson=a[a[x].ch[]].size,ls=qur(a[x].ch[]),rs=qur(a[x].ch[]);
bool lor=;
long long ms=merge(lor,x);
return ls+rs+min(lson*rson-ms,ms);
}
}
int main()
{
scanf("%d",&n);
build(root);
cout<<qur(root)<<endl;
return ;
}