分治专题 求排列的逆序数

求一个排序的逆序数：分治

利用分治排序的思想：nxs(l ,r)=nxs(l, m)+nxs(m, r)+nxs(左半边取一个数和右半边取一个数产生的)
 

#include<bits/stdc++.h>
using namespace std;

int a[100005];
int b[100005];

long long gbpx(int l, int r)
{
    long long sum=0;
    if(l==r)
        return 0;
    int mid=(l+r)/2;
    sum+=gbpx(l, mid);//左半边的逆序数
    sum+=gbpx(mid+1, r);//右半边的逆序数

    int i=l, j=mid+1, p=l;
    for(int x=i, y=j;x<=mid;x++)//左半边取一个数和右半边取一个数产生的
    {
        while(a[x]>a[y]&&y<r+1)
            y++;
        sum+=(y-j);
    }
    while(i<=mid&&j<=r)
    {
        if(a[i]>a[j])
            b[p++]=a[j], j++;
        else
            b[p++]=a[i], i++;
    }
    while(i<=mid)
    {
        b[p++]=a[i++];
    }
    while(j<=r)
    {
        b[p++]=a[j++];
    }
    for(int i=l;i<=r;i++)
    {
        a[i]=b[i];
    }

    return sum;

}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    cout<<gbpx(1, n)<<endl;

    return 0;
}

简便的方法：
#include<bits/stdc++.h>
using namespace std;

int a[100005];
int b[100005];
long long sum=0;

void gbpx(int l, int r)
{
    if(l==r)
        return;
    int mid=(l+r)/2;
    gbpx(l, mid);
    gbpx(mid+1, r);

    int i=l, j=mid+1, p=l;
    while(i<=mid&&j<=r)
    {
        if(a[j]>a[i])
            b[p++]=a[i++];
        else
            b[p++]=a[j++], sum+=mid+1-i;//直接求
    }
    while(i<=mid)
    {
        b[p++]=a[i++];
    }
    while(j<=r)
    {
        b[p++]=a[j++];
    }
    for(int i=l;i<=r;i++)
    {
        a[i]=b[i];
    }

}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    gbpx(1, n);
    cout<<sum<<endl;

    return 0;
}