题目描述
Ultra-QuickSort
解法：树状数组（C++）
详细参考 树状数组例题（poj2299）
#include <iostream>
#include <string.h>
#include <algorithm>using namespace std;const int N = 5e5+5;struct Node{
int val, pos;
}a[N];int c[N], index[N], n;bool cmp(const Node &x, const Node &y){
return x.val<y.val;}int lowbit(int x){
return x&(-x);}void add(int idx, int v)
{
for(int i=idx;i<=n;i+=lowbit(i))c[i] += v;
}int sum(int idx)
{
int s = 0;for(int i=idx;i;i-=lowbit(i))s += c[i];return s;
}int main()
{
while(scanf("%d", &n)==1 && n){
memset(c, 0, sizeof(c));for(int i=1;i<=n;i++){
scanf("%d", &(a[i].val));a[i].pos = i;}sort(a+1, a+n+1, cmp);for(int i=1;i<=n;i++)index[a[i].pos] = i;long long ans = 0;for(int i=1;i<=n;i++){
add(index[i], 1);ans += i - sum(index[i]);}printf("%lld\n", ans);}return 0;
}