求解逆序数的几种方法

逆序数：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。（摘自百度百科）

1.冒泡排序：（默认从小到大排序）上升过程每碰到一个比它大的逆序数+1，时间复杂度O（N^2），不推荐.

2.归并排序：序列1： 3 4 5 序列2 ： 2 3 6 7
由于归并过程中的两个序列都分别有序了，如果此时a[i]<a[j],此时序列的逆序数肯定不会增加
反之，如果 a[i] > a[j],此时a[j]要放到a[i]前面去,则[i,mid]的数都要比a[j]大，所以逆序数个数增加 mid-i+1个

时间复杂度O（N*logN）

http://poj.org/problem?id=1804

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int N = 1000010;
int a[N];
int temp[N];
int cnt;
void Merge(int left,int mid,int right){
    int i = left , j = mid+1, k = left;
    while(i<=mid&&j<=right){
        if(a[i]<=a[j]){
            temp[k++] = a[i++];
        }
        else{
            cnt +=(mid-i+1);
            temp[k++] = a[j++];
        }
    }
    while(i<=mid) temp[k++] = a[i++];
    while(j<=right) temp[k++] = a[j++];
    for(int i = left;i<=right;i++){ ///排好序的序列
        a[i] = temp[i];
    }
}
void Merge_Sort(int left,int right){
    if(left<right){
        int mid = (left+right)>>1;
        Merge_Sort(left,mid);
        Merge_Sort(mid+1,right);
        Merge(left,mid,right);
    }
}
int main()
{
    int tcase;
    int  k =1;
    scanf("%d",&tcase);
    while(tcase--){
        printf("Scenario #%d:
",k++);
        cnt = 0;
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        Merge_Sort(0,n-1);
        /*for(int i=0;i<n;i++){
            printf("%d",a[i]);
        }*/
        printf("%d

",cnt);
    }

}

3.树状数组：主要是离散化过程

这篇博客写得好

http://www.cnblogs.com/shenshuyang/archive/2012/07/14/2591859.html

http://acm.nyist.net/JudgeOnline/problem.php?pid=117

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int N = 1000010;
long long B[N],C[N];
struct arr{
    long long value;
    int id;
}a[N];
int n;
int cmp(arr p,arr q){
    if(p.value==q.value) return p.id<q.id;  ///如果值相同，按照输入相对位置排序，WA无限次
    return p.value < q.value;
}
int lowbit(int x){
    return x&(-x);
}
void update(int idx,int value){
    for(int i=idx;i<=n;i+=lowbit(i)){
        C[i]+=value;
    }
}
long long getsum(int idx){
    long long cnt = 0;
    for(int i=idx;i>=1;i-=lowbit(i)){
        cnt+=C[i];
    }
    return cnt;
}
int main()
{
    int tcase,k=1;
    scanf("%d",&tcase);
    while(tcase--){
        memset(C,0,sizeof(C));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i].value);
            a[i].id = i;  ///映射下标
        }
        sort(a+1,a+n+1,cmp);
        for(int i =1;i<=n;i++) B[a[i].id] = i; ///这步超巧妙,a.v与B数组刚好形成了一一映射的关系
        //for(int i=1;i<=n;i++) printf("%d",B[i]);
        long long cnt = 0;
        for(int i=1;i<=n;i++){
            update(B[i],1);
            cnt +=i - getsum(B[i]);
        }
        printf("%lld
",cnt);
    }

}