原题链接：http://poj.org/problem?id=2299

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is
sorted in ascending order. For the input sequence 
9 1 0 5 4 ,

Ultra-QuickSort produces the output 
0 1 4 5 9 .

Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

Input

Output

Sample Input

5
9
1
0
5
4
3
1
2
3
0

Sample Output

6
0

Source

//Accepted	3692 KB	391 ms	C++	750 B	2013-03-08 21:37:57
#include<cstdio>
#include<cstring>

const int maxn = 500000 + 10;

int a[maxn];
int t[maxn];
int n;
__int64 ans;

void merge_sort(int *a, int x, int y, int *t)
{
	if(y-x > 1)
	{
		int m = x + (y-x)/2;
		int p = x, q = m, i = x;
	 
		merge_sort(a, x, m, t);
		merge_sort(a, m, y, t);
		
		while(p < m && q < y) //合并 
		{
			if(a[p] <= a[q]) t[i++] = a[p++];
			else
			{
				t[i++] = a[q++];//a[p]>a[q]
				ans += m-p;
			} 
		}	
		while(p < m) t[i++] = a[p++];
		while(q < y) t[i++] = a[q++];
		
		for(i = x; i < y; i++) a[i] = t[i];
	}
}
int main()
{
	while(scanf("%d", &n) != EOF)
	{
		ans = 0;
		if(n == 0) break;
		
		for(int i = 0; i < n; i++)
			scanf("%d", &a[i]);
		
		merge_sort(a, 0, n, t);
		
		printf("%I64d\n", ans);	
	}
	return 0;
}

树状数组思路：树状数组+离散化

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int maxn = 500000+10;

__int64 c[maxn];
int b[maxn];
struct Node{
    int val; //元素值
    int index; // 编号
}a[maxn];
int n;

bool cmp(Node a, Node b) //从小到大排序
{
    return a.val < b.val;
}

int lowbit(int x)
{
    return x&(-x);
}

void add(int i, int val)
{
    while(i <= n)
    {
        c[i] += val;
        i += lowbit(i);
    }
}

__int64 sum(int i)
{
    __int64 ret = 0;
    while(i > 0) //下标从 1 开始
    {
        ret += c[i];
        i -= lowbit(i);
    }
    return ret;
}

int main()
{
    while(scanf("%d", &n) != EOF)
    {
        if(n == 0) break;

        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));

        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i].val);
            a[i].index = i;
        }
        sort(a+1, a+n+1, cmp); // 从小到大排序

        for(int i = 1; i <= n; i++) //离散化
        {
            b[a[i].index] = i; // b[i] 存原来编号为 i 的数现在第 b[i] 大
        }

        __int64 ans = 0;
        for(int i = 1; i <= n; i++)
        {
            add(b[i], 1); // 按照初始输入顺序依次在树状数组中插入元素
            ans += sum(n)-sum(b[i]); // 统计每个数前面比自己大的数的个数【目前总的个数减去小于等于当前数值的数目】
            //ans += i - sum(b[i]); 也一样
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

利用树状数组离散化求逆序数，看了很久，还是无法完全理解，贴个KB神的用树状数组求解的代码吧。。。

http://www.cnblogs.com/kuangbin/archive/2012/08/09/2630042.html

/*
POJ 2299 Ultra-QuickSort
求逆序数
离散化+树状数组
首先从小到大进行编号，从而实现离散化
然后利用树状数组来统计每个数前面比自己大的数的个数
*/

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=500010;
int c[MAXN];
int b[MAXN];
int n;
struct Node
{
    int index;//序号
    int v;
}node[MAXN];
bool cmp(Node a,Node b)
{
    return a.v<b.v;
}
int lowbit(int x)
{
    return x&(-x);
}
void add(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;
}
int main()
{
   // freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d",&n),n)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&node[i].v);
            node[i].index=i;
        }
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        //离散化
        sort(node+1,node+n+1,cmp);
        //将最小的编号为1
        b[node[1].index]=1;
        for(int i=2;i<=n;i++)
        {
            if(node[i].v!=node[i-1].v) b[node[i].index]=i;
            else b[node[i].index]=b[node[i-1].index];
        }
        long long  ans=0;
        //这里用的很好
        //一开始c数组都是0，然后逐渐在b[i]处加上1；
        for(int i=1;i<=n;i++)
        {
            add(b[i],1);
            ans+=i-sum(b[i]);  //统计每个数前面比自己大的数的个数 
        }
        printf("%I64d\n",ans);
    }
    return 0;
}