Nemo_ @ 2023-07-13 15:13:04
#include<bits/stdc++.h>
using namespace std;
long int p[500010];
long int a[500010];
long long n,sum;
void msort(int s,int t)
{
if(s==t) return ;
int mid=(s+t)/2;
int i=s,j=mid+1,k=s;
msort(s,mid);
msort(mid+1,t);
while(i<=mid&&j<=t)
{
if(a[i]<=a[j])
{
p[k]=a[i];
k++;i++;
}
else
{
p[k]=a[j];
j++;k++;
sum+=mid-i+1;
}
}
while(i<=mid)
{
p[k]=a[i];
k++;i++;
}
while(j<=t)
{
p[k]=a[i];
k++;j++;
}
for(int m=s;m<=t;m++)
{
a[m]=p[m];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
msort(1,n);
printf("%lld",sum);
return 0;
}
by KidzzZip @ 2023-07-14 17:03:32
#include<bits/stdc++.h>
using namespace std;
long long p[500010];
long long a[500010];
long long n,sum=0;
void msort(int s,int t)
{
if(s>=t) return ;//problem 1 源码:if(s==t) return;
int mid=(s+t)/2;
int i=s,j=mid+1,k=s;
msort(s,mid);
msort(mid+1,t);
while(i<=mid&&j<=t)
{
if(a[i]<=a[j])
{
p[k]=a[i];
k++;i++;
}
else
{
p[k]=a[j];
j++;k++;
sum=sum+mid-i+1;
}
}
while(i<=mid)
{
p[k]=a[i];
k++;i++;
}
while(j<=t)
{
p[k]=a[j];
k++;j++;
// 源码:k++;j++;
//problem 2
}
for(int m=s;m<=t;m++)
{
a[m]=p[m];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
msort(1,n);
printf("%lld",sum);
return 0;
}