poj 2299 Ultra-QuickSort 求逆序数 树状数组解法

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 500005;

struct number
{
    int a, b, pos;
}num[maxn];  //这个结构体是为离散化创建的，

int t[maxn];
int n;
int lowbit(int x)
{
    return x&(-x);
}

void update(int x)
{
    while (x <= n)
    {
        t[x] += 1;
        x += lowbit(x);
    }
}

int getsum(int x)
{
    int s = 0;
    while (x)
    {
        s += t[x];
        x -= lowbit(x);
    }
    return s;
}

int cmp(number x, number y)
{
    return x.a < y.a;
}

int cmp2(number x, number y)
{
    return x.pos < y.pos;
}

int main()
{
    while (scanf("%d", &n) && n)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d",&num[i].a);
            num[i].pos = i;
        }
        sort(num+1, num+1+n, cmp);
        for (int i = 1; i <= n; i++)
            num[i].b = i;
        sort(num+1, num+1+n, cmp2);  //两次的排序就是离散化的过程
        memset(t, 0, sizeof(t));
        __int64 sum = 0;
        for (int i = 1; i <= n; i++)
        {
            sum += (__int64)(i - 1 - getsum(num[i].b));
            update(num[i].b);
        }
        printf("%I64d\n",sum);
    }
    return 0;
}