求逆序对个数
#include<cstdio>
#define N 500010
using namespace std;
typedef long long ll;
ll n,a[N],b[N],ans;
void Merge_sort(ll a[],ll b[],ll l,ll r)
{
ll mid=l+r>>1,p=l-1,i,j;
if (l<r)
{
Merge_sort(a,b,l,mid),Merge_sort(a,b,mid+1,r);
for (i=l,j=mid+1;i<=mid && j<=r;)
if (a[i]<a[j]) b[++p]=a[i++];
else b[++p]=a[j++],ans+=mid-i+1;
while (i<=mid) b[++p]=a[i++];
while (j<=r) b[++p]=a[j++];
for (i=l;i<=r;i++)
a[i]=b[i];
}
}
int main()
{
while (scanf("%lld",&n)!=EOF && n)
{
ans=0;
for (int i=1;i<=n;i++)
scanf("%lld",a+i);
Merge_sort(a,b,1,n);
printf("%lld
",ans);
}
return 0;
}