Ultra-QuickSort

我是题目链接](http://poj.org/problem?id=2299)
设A为有n个数字的有序集(n>1)，其中所有数字各不相同。如果存在正整数i, j使得1 ≤iA[j]，则这个有序对称为A的一个逆序对，也称作逆序数。
在这个问题中，你需要快速的求出一个给定数组中逆序对的数量

Input
输入包含多个测试用例，每个测试用例第一行为一个整数n（n<500000）表示数组的长度，下面n行每一行包含一个整数0≤a[i]≤999,999,999，即数组中第i个元素的值。当n=0时结束输入
Output
对于输入的每个数组，程序应该输出该数组中逆序对的数量

Sample Input
5
9
1
0
5
4
3
1
2
3
0

Sample Output
6
0
解题思路：
树状数组可以以nlogn的时间复杂度求序列的逆序对；

//树状数组
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 500010
#define ll long long
int c[MAX];
int aa[MAX];
int n;
struct node{
    int val;
    int order;
}in[MAX];//结构体存入
int lowbit(int x)//
{
    return x&(-x);
}
//void update(int x,int val)//修改
//{
//    while(x<=n){
//        c[x]+=val;
//        x+=lowbit(x);
//    }
//}
void update(int x,int val)
{
    for(int j=x;j<=n;j+=lowbit(j))
    {
        c[j]+=val;
    }
}
//int sum(int x)
//{
//    int s=0;
//    while(x>=1)
//    {
//        s+=c[x];
//        x-=lowbit(x);
//    }
//    return s;//一开始竟然忘记写了这个语句，还以为树状数组写错了呢
//}
int sum(int k)//求和
{
    int ans=0;
    for(int i=k;i>0;i-=lowbit(i))
    {
        ans+=c[i];
    }
    return ans;
}

bool cmp(node a,node b){
    return a.val<b.val;
}
int main()
{
    while(scanf("%d",&n)==1&&n){
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&in[i].val);
            in[i].order=i;
        }
        sort(in+1,in+n+1,cmp);
        for(int i=1;i<=n;++i)
            aa[in[i].order]=i;//离散化到小范围来
        memset(c,0,sizeof(c));
       ll ans=0;
        for(int i=1;i<=n;++i)
        {
            update(aa[i], 1);
            ans+=(i-sum(aa[i]));
        }
        cout<<ans<<endl;
    }
    return 0;
}