题目链接：http://poj.org/problem?id=2299
题目大意：给定n个数，要求这些数构成的逆序对的个数。
可以采用归并排序，也可以使用树状数组
可以把数一个个插入到树状数组中， 每插入一个数， 统计比他小的数的个数，对应的逆序为 i- getsum( data[i] )，其中 i 为当前已经插入的数的个数， getsum( data[i] ）为比 data[i] 小的数的个数，i- getsum( data[i] ) 即比 data[i] 大的个数， 即逆序的个数。最后需要把所有逆序数求和，就是在插入的过程中边插入边求和。
然而如果数据比较大该怎么办呢？我们就有必要进行一下离散化了
比如 10 30 20 40 50
和 1 3 2 4 5
在求逆序数时他们的意义是一样的。我们可以先快排一次，然后利用hash进行数据离散化处理。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAX=;
int N;
struct Node{int data,pos;}d[MAX];
int p[MAX];
bool cmp(Node a,Node b)
{
return a.data<b.data;
}
class BIT
{
private:
int bit[MAX];//存的是个数，下标是那个数
int lowbit(int i)
{
return i&-i;
}
public:
BIT()
{
memset(bit,,sizeof(bit));
}
void update(int i,int v)
{
while(i<=MAX)
{
bit[i]+=v;
i+=lowbit(i);
}
}
int getsum(int i)
{
int s=;
while(i>)
{
s+=bit[i];
i-=lowbit(i);
}
return s;
}
};
int main()
{
while(cin>>N&&N)
{
for(int i=;i<=N;i++)
{
scanf("%d",&d[i].data);
d[i].pos=i;
}
sort(d+,d+N+,cmp);
memset(p,,sizeof(p));
for(int i=;i<=N;i++)//坐标离散化
{
p[d[i].pos]=i;
}
__int64 ans=;
BIT tree;
for(int i=;i<=N;i++)
{
tree.update(p[i],);
ans+=(__int64)(i-tree.getsum(p[i]));//求逆序数
}
printf("%I64d\n",ans);
}
return ;
}