POJ2299 Ultra-QuickSort（离散化 树状数组）

February 14, 2016

题目链接

题意：求 n 个数的逆序对数。

思路：首先 n 只有 500000，然而数字范围非常大，将输入离散化成 1~500000 范围的数，离散化后的数组为 li[]，li[1]为第一个进入数，将 li[i]对应的树状数组更新为 1，判断 1~li[i]间有几个数已进入（有为 1，无为 0，就是 sum），i-sum(li[i])就是逆序对数。

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int a[500005];
int li[500005];
struct node{
    int order;
    int num;
}N[500005];
bool cmp(node x, node y){
    return x.num<y.num;
}
int lowbit(int x){
    return x&(-x);
}
void add(int pos , int num){
    while(pos <= n){
        a[pos] += num;
        pos += lowbit(pos);
    }
}
int sum(int n){
    int sum = 0;
    while(n > 0){
        sum += a[n];
        n -= lowbit(n);
    }
    return sum;
}
int main(){
    //freopen("a.txt", "r", stdin);
    while(scanf("%d", &n) != EOF && n){
        for(int i = 1; i <= n; i++){
            scanf("%d", &N[i].num);
            N[i].order = i;
        }
        sort(N+1, N+n+1, cmp);
        for(int i = 1; i <= n; i++)
            li[N[i].order] = i;
        memset(a, 0, sizeof(a));
        long long ans = 0;

        for(int i = 1; i <= n; i++){
            add(li[i], 1);
            ans += i-sum(li[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]