求逆序对数，树状数组
数据范围较大，要离散化。
给每一个数据一个id， 第i个数据的id为i。 然后从小到大排序，对于每个id做 ans += read(n) - read(array[i].id)，read(n) - read(array[i].id)表示原来在当前数的后面（其id大于当前数的id），
现在在当前数前面的数个数，也就是逆序对数。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXVAL = 500005;
int tree[MAXVAL] ;
struct Type
{
int num, id;
};
int n;
Type array[MAXVAL];
void update(int idx, int inc) //更新idx的频率
{
while(idx <= n)
{
tree[idx] += inc;
idx += (idx & - idx);
}
}
int read(int idx) //读取1--idx的频率和
{
int sum = 0;
while(idx > 0)
{
sum += tree[idx];
idx -= (idx & - idx);
}
return sum;
}
int readSingle(int idx) // 读取某个位置的频率， O(lg MAXVAL)
{
int sum = tree[idx];
if(idx > 0)
{
int z = idx - ( idx & - idx);
idx --;
while( idx != z)
{
sum -= tree[idx];
idx -= (idx & - idx);
}
}
return sum;
}
bool cmp(const Type &a, const Type &b)
{
return a.num < b.num;
}
int main()
{
while (scanf("%d",&n) && n != 0)
{
memset(array, 0, sizeof (array));
memset(tree, 0, sizeof tree);
// read the data
for(int i = 1; i <= n; i ++)
{
scanf("%d",&array[i].num);
array[i].id = i;
}
sort(array + 1, array + 1 + n, cmp);
long long ans = 0;
for(int i = 1; i <= n; i ++)
{
//printf( "cal %d \n",read(n) - read(array[i].id));
ans += read(n) - read(array[i].id);
update( array[i].id, 1);
}
cout << ans << endl;
}
return 0;
}