POJ 2299 Ultra-QuickSort（树状数组）

求逆序数，记录一下原来的位置，快排一下看看每个位置的数应该排在什么地方，然后从第一个数开始把它排序后的位置放入树状数组，并且可以算出在这之前的数有多少个没有放在这个数前面（已放入的数量-在我前面的数量），也就是逆序数

C++ Code

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define M 500005

using namespace std;

struct node{
    int num;
    int order;
    bool operator<(const node &b) const{
        return num < b.num;
    }
}arr[M];

int ranks[M];
int cnt[M];
int num;

int lowbit(int x){
    return (x & (-x));
}

void update(int pos, int x){
    while(pos <= num){
        cnt[pos] += x;
        pos += lowbit(pos);
    }
}

int getSum(int pos){
    int ans = 0;
    while(pos >= 1){
        ans += cnt[pos];
        pos -= lowbit(pos);
    }
    return ans;
}

int main(){
    while(~scanf("%d", &num) && num != 0){
        for(int i = 1; i <= num; i++){
            scanf("%d", &arr[i].num);
            arr[i].order = i;
        }
        sort(arr + 1, arr + 1 + num);
        for(int i = 1; i <= num; i++){
            ranks[arr[i].order] = i;
        }
        memset(cnt, 0, sizeof(cnt));
        long long ans = 0;
        for(int i = 1; i <= num; i++){
            update(ranks[i], 1);
            ans += (i - getSum(ranks[i]));
        }
        printf("%lld\n", ans);
    }
    return 0;
}