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;
}