学步园

题意：求长度为n（n < 500000），元素范围为[0, 999999999]的数组的逆序对数。

题目链接：http://poj.org/problem?id=2299

——>>设x[i]表示数i已经出现的次数，从后往前扫描，对于每个数k，那么k产生的逆序对数为x[0] + x[1] + ... + x[k-1]，于是可以用树状数组了。

——>>由于元素范围可到999999999，所以应做离散化操作。

——>>如果所有数逆序出现，那么逆序对数最多为n(n-1)/2，代入n = 500000可知已超32位整数范围，应用64位整数。

第一次用了STL的unique和resize还有map，TLE了。。。第二次，全改了。。。T_T。。。

#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int maxn = 500000 + 10;

int n;
long long c[maxn];

typedef struct CNode {
    int id;
    int v;
    bool operator < (const CNode& e) const {
        return v < e.v || (v == e.v && id < e.id);
    }
} Node;

Node a[maxn];
int p[maxn];

int lowerbit(int x) {
    return x & (-x);
}

long long sum(int x) {
    long long ret = 0;
    while(x > 0) {
        ret += c[x];
        x -= lowerbit(x);
    }
    return ret;
}

void add(int x) {
    while(x <= n) {
        c[x]++;
        x += lowerbit(x);
    }
}

int main()
{
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++) {
            scanf("%d", &a[i].v);
            a[i].id = i;
        }

        sort(a, a+n);
        int stamp = 1;
        p[a[0].id] = stamp;
        for(int i = 1; i < n; i++) {
            if(a[i].v > a[i-1].v) stamp++;
            p[a[i].id] = stamp;
        }
        memset(c, 0, sizeof(c));
        long long ret = 0;
        for(int i = n-1; i >= 0; i--) {
            ret += sum(p[i]-1);
            add(p[i]);
        }
        printf("%I64d\n", ret);
    }
    return 0;
}