10810-Ultra-QuickSort【逆序数、树状数组离散化】

求逆序数的模板题

我自己用的是树状数组求得，因为a[i]值最多为999999999，但是最多只有500000个元素，所以需要离散化一下

看网上还有别的算法，感觉都差不多，都是nlogn的算法

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 555555;
LL array[maxn];
LL hash[maxn];
int C[maxn];
int n;
int lowbit(int x){
    return x & -x;
}
void add(int x,int d){
    while(x <= n){
        C[x] += d;
        x += lowbit(x);
    }
}
int sum(int x){
    int ret = 0;
    while(x > 0){
        ret += C[x];
        x -= lowbit(x);
    }
    return ret;
}
void get_hash(){
    for(int i = 0; i < n; i++){
        LL e = hash[i];
        int pos = lower_bound(array,array + n,e) - array;
        //printf("%d ",pos);
        hash[i] = pos + 1;
    }
}
void solve(){
    LL ans = 0;
    for(int i = 0; i < n; i++){
        int e = (int)hash[i];
        //printf("%d\n",e);
        ans += (sum(n) - sum(e - 1));
        //printf("%d %d\n",e,ans);
        add(e,1);
    }
    printf("%lld\n",ans);
}
int main(){
    while(scanf("%d",&n) && n){
        memset(C,0,sizeof(C));
        for(int i = 0; i < n; i++){
            scanf("%lld",&array[i]);
            hash[i] = array[i];
        }
        sort(array,array + n);
        get_hash();
        solve();
    }
    return 0;
}

10810-Ultra-QuickSort【逆序数、树状数组离散化】

原文：http://blog.csdn.net/u013451221/article/details/44654199