用树状数组。
看题意，它要求排序的次数……我一开始想的是……这TM不就是冒泡排序……
直接上冒泡啊，排一次cnt ++ 多简单……
事实无情的给了我响亮的一巴掌……啊！多么年少无知天真无暇的我啊……
事实就是这TM会TLE……
好吧，换用树状数组【Empty大神果然慧眼识珠，知道这题非用不可啊……
分析一下，其实是求某个数的逆序数，这样的话就应该很简单了……吧
事实再次证明我是多么的单纯啊……
必须得离散化……所谓离散化， 就是把数据集中但是又不改变数据的相对大小…… 比如样例 9 1 0 5 4 离散化之后就是 5 2 1 4 3……
然后才能AC ……
AC Memory : 8100 KB Time : 407 ms
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
int a[500005];
int c[500005];
struct Node
{
int v,order;
} in[500005];
int lowbit(int x)
{
return x&(-x);
}
void update(int i,int val)
{
while(i<=n)
{
c[i]+=val;
i+=lowbit(i);
}
}
int sum(int i)
{
int s = 0;
while(i>0)
{
s+=c[i];
i-=lowbit(i);
}
return s;
}
bool cmp(Node a,Node b)
{
return a.v <b.v;
}
int main()
{
while(scanf("%d",&n),n)
{
memset(a, 0, sizeof(a));
memset(c, 0, sizeof(c));
for(int i = 1;i<=n;i++)
{
scanf("%d",&in[i].v);
in[i].order = i;
}
sort(in+1,in+n+1,cmp);
a[in[1].order] = 1;
for(int i = 2; i <= n; i++)
{
if(in[i].v != in[i-1].v)
a[in[i].order] = i;
else
a[in[i].order] = a[in[i-1].order];
}
long long res = 0;
for(int i = 1;i<=n;i++)
{
update(a[i],1);
res+=i-sum(a[i]);
}
printf("%I64d\n",res);
}
return 0;
}