【洛谷】P1908逆序对
程序员文章站
2022-05-10 20:17:03
...
这就是归并排序求逆序对啦!
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=40000+10;
int a[MAXN],ans;
int tmp[MAXN];
void merge(int l,int r)
{
int mid=((l+r)>>1);
if(l==r)return;
merge(l,mid);
merge(mid+1,r);
int i,j;
int k=l-1;
i=l;j=mid+1;
while(i<=mid&&j<=r)
{
if(a[i]>a[j])
{
k++;
tmp[k]=a[j++];
ans+=(mid-i)+1;
}
else
{
k++;
tmp[k]=a[i++];
}
}
while(i<=mid)tmp[++k]=a[i++];
while(j<=r)tmp[++k]=a[j++];
for(i=l;i<=r;i++)
a[i]=tmp[i];
}
int main()
{
int t,i,j;
int n;
// freopen("Mogic.in","r",stdin);
// freopen("Mogic.out","w",stdout);
memset(a,0,sizeof(a));
scanf("%d",&n);
for(j=1;j<=n;j++)
scanf("%d",&a[j]);
ans=0;
merge(1,n);
printf("%d\n",ans);
return 0;
}