P1908 逆序对-（cdq分治）

https://www.luogu.org/problem/P1908

沿用归并排序的思想求逆序对。

坑1：结果爆int型，需要用longlong

坑2：相对于归并排序，在比较的时候多了一个等号

举例说明归并排序解本题，例如有6个数，

36，87，99，左区间范围是l到mid，下标用t1表示

1，2，50，右区间范围是mid+1到r，下标用t2表示

分成2堆，两堆排好序，要合并。此时l=1,mid=3,t1=1; mid+1=4,r=6,t2=4;

比较36和1，选1，则左边还没有排序的数都和1构成逆序对，3个，36，87，99，mid-t1+1=3；

比较36和2，选2，则左边还没有排序的数都和2构成逆序对，3个，36，87，99，mid-t1+1=3；

比较36和50，选36，则没有构成逆序对；

比较87和50，选50，则左边还没有排序的数都和50构成逆序对，2个，87，99，mid-t1+1=2；

右区间已经排完，直接选左区间的数，没有构成逆序对。

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<math.h>

#include<string>

#include<map>

#include<queue>

#include<stack>

#include<set>

#include<ctime>

#define ll long long

#define inf 0x3f3f3f3f

const double pi=3.1415926;

using namespace std;

const int maxx=500005;

int a[maxx];///排序数组

int b[maxx];///原数组

int n;

ll ans=0;

void cdq(int l,int r,int x[])///左右闭区间，x数组作为参数，传入

{

    if(l==r)

        return;//出口

    int mid=(l+r)/2;

    cdq(l,mid,x);

    cdq(mid+1,r,x);

    int t1=l,t2=mid+1;///左右指针

    for(int i=l;i<=r;i++)

    {

        ///(当前左子区间的值<=当前右区间的值 并且 左指针还没有超出左边的最大值) 或者 右边已经排完了  就取左边

        if( (x[t1]<=x[t2] && t1<=mid) || t2>r )//被这个等于号坑了好久

            a[i]=x[t1++];

        else ///不取左就取右 个数则由for循环保证

        {

            a[i]=x[t2++];

            ans+=(ll)(mid-t1+1);///如果左区间还有剩，那就是和 当前t2下标的这个数构成逆序对

        }

    }

    for(int i=l;i<=r;i++)///对b数组也进行交换

        x[i]=a[i];

}

int main()///P1908

{

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%d",&b[i]);

    cdq(1,n,b);

    printf("%lld\n",ans);

    return 0;

}

巴特西

P1908 逆序对-（cdq分治）

最新文章

热门文章