题意：求长度为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;
}