求逆序对数的方法(归并排序 and 树状数组)

水深无声 2022-05-29 06:24 192阅读 0赞

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。比如一个序列为4 5 1 3 2， 那么这个序列的逆序数为7，逆序对分别为(4, 1), (4, 3), (4, 2), (5, 1), (5, 3), (5, 2),(3, 2)。

输入描述:

第一行有一个整数n(1 <= n <= 100000),  然后第二行跟着n个整数，对于第i个数a[i]，(0 <= a[i] <= 100000)。

## 输出描述: ##

输出这个序列中的逆序数

## 输入 ##

5
    4 5 1 3 2

## 输出 ##

方法1(树状数组):所求的交换次数等价于满足i<j&&a\[i\]>a\[j\]的数对的个数，而对与每一个j如果我们能快速的求出满足i<j&&a\[i\]>a\[j\]的i的个数。我们构建一个1到n的BIT,按照j=0 ,1,,,n-1的顺序操作：

1：把j-(BIT查询的到的前aj项和）加入答案

2：把BIT中aj位置加一

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #define ll long long
    using namespace std;
    
    const int maxn=1e5+100;
    ll a[maxn],bit[maxn],n;
    
    ll lowbit(ll x)
    {
        return x&(-x);
    }
    ll sum(ll x)
    {
        ll s=0;
        while (x>0) {
            s+=bit[x];
            x-=lowbit(x);
        }
        return s;
    }
    void add(ll x,ll val)
    {
        while (x<=n) {
            bit[x]+=val;
            x+=lowbit(x);
        }
    }
    int main()
    {
        cin>>n;
        for (int i=0;i<n;i++){
            cin>>a[i];
        }
        ll ans=0;
        for (int i=0;i<n;i++) {
            ans+=i-sum(a[i]);
            add(a[i],1);
        }
        cout<<ans<<endl;
    }

方法2(归并排序):

\[　　　　　数列A　　　　　］

［数列Ｂ　　］［数列Ｃ　　］

假设我们要统计数列Ａ中逆序对的个数，于是数列Ａ所有的逆序对必居下面三者其一

１：i与j都属于数列B

2：i与j都属于数列C

3:i属于数列B，j属于数列C

代码如下:

#include<iostream>
    #include<cmath>
    #include<cstring>
    #include<cstdio>
    #include<vector>
    #define ll long long
    using namespace std;
    
    
    vector<int> vec;
    
    ll Merge_sort(vector<int> &a)
    {
        int n=a.size();
        if (n<=1) return 0;
        ll cnt=0;
        vector<int> b(a.begin(),a.begin()+n/2);
        vector<int> c(a.begin()+n/2,a.end());
        cnt+=Merge_sort(b);
        cnt+=Merge_sort(c);
    
        int ai=0,bi=0,ci=0;
        while (ai<n) {
           if (bi<b.size()&&(ci==c.size()||b[bi]<=c[ci])) {
                a[ai++]=b[bi++];
            }
            else {
                cnt+=n/2-bi;
                a[ai++]=c[ci++];
            }
        }
        return cnt;
    }
    int main()
    {
        int n;
        cin>>n;
        for (int i=0;i<n;i++) {
            int a;
            cin>>a;
            vec.push_back(a);
        }
        cout<<Merge_sort(vec)<<endl;
        return 0;
    }