SGU 180 Inversions

点击打开sgu 180

思路: 树状数组+离散化

分析:

1 题目给定n个数，每个数最大为10^9 , 最小为0，求多少个匹配使得1<=i<j<=n并且A[i] > A[j]

2 因为数的最大值为10^9.所以我们应该利用离散化的思想。然后在利用树状数组求个数即可

3 注意由于输入的值由可能为0，我们应该在输入的时候就把所有的值加上1

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 66000;

int n;
int num[MAXN];
int treeNum[MAXN];

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

int getSum(int x){
    int sum = 0;
    while(x){
        sum += treeNum[x];
        x -= lowbit(x);
    }
    return sum;
}

void add(int x , int val){
    while(x < MAXN){
         treeNum[x] += val;
         x += lowbit(x);
    }
}

int search(int x){
    int left = 0;
    int right = n-1;
    while(left <= right){
        int mid = (left+right)>>1;
        if(num[mid] == x)
            return mid+1;
        else if(num[mid] < x)
            left = mid+1;
        else
            right = mid-1;
    }
}

long long solve(){
    int tmp[MAXN];
    memcpy(tmp , num , sizeof(num));
    sort(num , num+n);
    long long ans = 0;
    for(int i = 0 ; i < n ; i++){
        int x = search(tmp[i]);
        ans += i-getSum(x);
        add(x , 1);
    }
    return ans;
}

int main(){
    int x;
    while(scanf("%d" , &n) != EOF){
         memset(treeNum , 0 , sizeof(treeNum));
         for(int i = 0 ; i < n ; i++){
             scanf("%d" , &num[i]);
             num[i]++;
         }
         printf("%lld\n" , solve());
    }
    return 0;
}