求逆序对

Problem Description

给定一个序列a1,a2,...,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。 (n<=100000,ai<=100000)

Input

输入有多组数据，每组数据第1行为n，表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。

Output

对于每组数据输出所有逆序对的总数。

Sample Input

4
3
2
3
2

Sample Output

3

//  关键字：归并排序；

//标程：

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int a[110000];
__int64 num;
void calculate(int *p,int l,int mid,int r)
{
    int *b = new int[r + 1]; 
    int i,j,k;
    for (i = l;i <= r;++i)
    {
        b[i] = p[i];
    }
     i = l,j = mid + 1,k = l;
    while (i <= mid && j <= r)
    {
        if (b[i] <= b[j])
             p[k++] = b[i++];
        else
        {
            p[k++] = b[j++];
            num += mid - i + 1;       
        }
    }
    while (i <= mid)   p[k++] = b[i++];     
    while (j <= r)  p[k++] = b[j++];      
    delete []b;
}
void dg(int *p,int l,int r)
{
	int mid;
	if(l<r)
	{
		mid = (l + r) / 2;
		dg(p,l,mid);
		dg(p,mid + 1,r);
		calculate(p,l,mid,r);
	}
}
int main()
{
//	freopen("b.txt","r",stdin);
    int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i = 0; i < n; i ++)
		   scanf("%d",&a[i]);
		num = 0;
        dg(a,0,n-1);
        printf("%I64d
",num);
	}
	return 0;
}