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

题目链接

      逆序的概念大家都知道，一个数到逆序数就是该数左边大于它到数的个数。

      很多没学过数据结构的人一上来肯定就是一个个数了，看看数据量500k，显然这种暴力的方法是行不通的。

      我们换种想法，可以在输入过程中对每个数的逆序数求解，建一个vis数组（初始化为0），只要输入一个数，在它的位置标记为1，然后计算出它的左边一共有多少数被标记了就可以知道多少个数比他小了，当然逆序数也就知道了，求从左到右数的和，这是树状数组最擅长的了。

      但我们看看每个数的范围是0 ≤ a[i] ≤ 999,999,999，我们不可能开那么大的数组，即使开的了也会浪费很多，这个时候我们就要对数据进行离散化处理了。

      所谓离散化，我们的了解就是对原数组排序，然后用所在位置的下标代替原数，这样我们就可以把数据范围缩小到1-500000，这个数组是开的下的。

代码：

#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;
}

关于这个题，还有归并排序的解法，虽然内存用的少了，但耗时增加了。