题目是快速排序，可用的居然是合并排序，排序中计算逆序数即可。。。

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

long long int count;

void Merge(long long int a[],long long int p,long long int k,long long int q)
{
    long long int num1=k-p+1;
    long long int num2=q-k;
    long long int i;
    long long int* b1=new long long int[num1+1];
    long long int* b2=new long long int[num2+1];
    for (i=0;i<num1;i++)
    {
        b1[i]=a[p+i];
    }
    b1[i]=9999999999;
    for (i=0;i<num2;i++)
    {
        b2[i]=a[k+i+1];
    }
    b2[i]=9999999999;
    int j=0;i=0;
    for(long long int kk=p;kk<=q;kk++)   
    {
        if (b1[i]<=b2[j])
        {
            a[kk]=b1[i];
            i++;
        }
        else
        {
            a[kk]=b2[j];
            j++;
            count+=(num1-i);    //求逆序数，即若b中有元素比a小，插入后共有a数组大小减去当前指向a的位置个逆序
        }
    }
    delete [] b1;
    delete [] b2;
}
void MergeSort(long long int a[],long long int p,long long int q)
{
    if (p<q)
    {
        long long int k=(p+q)/2;
        MergeSort(a,p,k);
        MergeSort(a,k+1,q);
        Merge(a,p,k,q);
    }
}
int main()
{
    long int num;
    while (scanf("%ld",&num)!=EOF&&num)
    {
        long long int* input=new long long int[num];
        count=0;
        for (int i=0;i<num;i++)
        {
           scanf("%lld",&input[i]);
        }
        MergeSort(input,0,num-1);
        printf("%lld\n",count);
         delete [] input;
    }
    
}