欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

归并排序求逆序对模板

程序员文章站 2022-05-10 15:05:48
...
//还是自己菜最后还是看了网上模板才写出来的

#include <bits/stdc++.h>

#define LL long long
using namespace std;

const int N=1e6+10;
LL num[N],a[N];
LL ans;
void Merge(int l,int mid,int r) //分治的治  合并是求逆序对的关键
{
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
    {
        if(num[i]>num[j]) //前半部分中比num[i]大的数都比num[j]大,将num[j]放在num[i]前面的话,逆序数要加上mid+1-i
        {
            a[k++]=num[j++];
            ans+=mid-i+1;  //统计逆序对
        }
        else   //这里这情况不产生逆序对
            a[k++]=num[i++];
    }
    while(i<=mid)
        a[k++]=num[i++];
    while(j<=r)
        a[k++]=num[j++];
    for(int e=l;e<=r;e++) //将这次操作完的num数组更新
        num[e]=a[e];
}

void Merge_sort(int l,int r) //分治的分 在这里不断地把一个串细分然后回溯合并
{
    if(l<r)
    {
        int mid=(l+r)/2;
        Merge_sort(l,mid);
        Merge_sort(mid+1,r);
        Merge(l,mid,r);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n&&n)
    {
        for(int i=0;i<n;i++)
            cin>>num[i];
        ans=0;
        Merge_sort(0,n-1);
        cout<<ans<<endl;
    }
    return 0;
}