POJ2299 Ultra-QuickSort(离散化 树状数组)

题目链接

题意:求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;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 树状数组  离散化