求逆序?qū)?shù)，樹狀數(shù)組
數(shù)據(jù)范圍較大，要離散化。
給每一個(gè)數(shù)據(jù)一個(gè)id， 第i個(gè)數(shù)據(jù)的id為i。 然后從小到大排序，對(duì)于每個(gè)id做 ans += read(n) - read(array[i].id)，read(n) - read(array[i].id)表示原來在當(dāng)前數(shù)的后面（其id大于當(dāng)前數(shù)的id），
現(xiàn)在在當(dāng)前數(shù)前面的數(shù)個(gè)數(shù)，也就是逆序?qū)?shù)。
#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) // 讀取某個(gè)位置的頻率， 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;
}