题目链接： http://poj.org/problem?id=2299
题目大意：给N个不同的数，求这N个数的逆序数。 （ n < 500,000， 0 ≤ a[i] ≤ 999,999,999） 树状数组求逆序数思路： 输入第i个数，更新树状数组（插入a[i]），然后查询在i之前的比a[i]小的数的个数tmp，i - tmp 即在a[i]之前比a[i]大的数。
另外， 本题 a[i] 的范围比较大，所以将其离散化，例如， 9, 1, 0, 5 , 4 ，可映射为： 5, 2, 1, 4, 3，相对大小没有改变，不影响逆序数个数， 具体操作看代码：
#include <cstdio> #include <vector> #include <algorithm> #include <cstring> using namespace std; struct Node{ int pos, val; Node(int x, int y){ val = x; pos = y; } bool operator < (const Node &p)const{ return val < p.val; } }; vector<Node> node; const int maxn = 500000 + 10; int c[maxn]; int N; int re[maxn]; int lowbit(int k){ return k & (-k); } void add(int pos){ while(pos <= N){ c[pos] += 1; pos += lowbit(pos); } } int sum(int x){ int tmp = 0; while(x > 0){ tmp += c[x]; x -= lowbit(x); } return tmp; } int main(){ while(scanf("%d", &N), N){ node.clear(); memset(c, 0, sizeof(c)); memset(re, 0, sizeof(re)); int val; for(int i = 1; i <= N; i++){ scanf("%d", &val); node.push_back(Node(val, i)); } sort(node.begin(), node.end()); long long ans = 0; for(int i = 0; i < N; i++){ re[node[i].pos] = i + 1; } for(int i = 1; i <= N; i++){ add(re[i]); ans += (i - sum(re[i])); } printf("%lld\n", ans); } return 0; }