lizichang @ 2021-09-07 22:38:45
#include<bits/stdc++.h>
using namespace std;
int a[500005],c[500005],n;
long long ans=0;
void m(int l,int r)
{
if(l==r) return ;
int mid=(l+r)/2;
int i=l,j=mid+1,k=r;
m(l,mid);
m(mid+1,r);
while(i<=mid&&j<=r)
if(a[i]<=a[j]) c[k++]=a[i++];
else c[k++]=a[j++],ans+=mid-i+1;
while(i<=mid) c[k++]=a[i++];
while(j<=l) c[k++]=a[j++];
for(int x=l;x<=r;x++) a[x]=c[x];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
m(1,n);
printf("%lld",ans);
return 0;
}
by cyhyyds @ 2021-09-07 22:42:11
while(j<=l)
?
by lizichang @ 2021-09-07 22:47:41
该改了之后,似乎还不对
by lizichang @ 2021-09-08 20:47:21
#include<bits/stdc++.h>
using namespace std;
long long a[500005],c[500005],n;
long long ans=0;
void m(int l,int r)
{
if(l==r) return ;
int mid=(l+r)/2;
int i=l,j=mid+1,k=r;
m(l,mid);
m(mid+1,r);
while(i<=mid&&j<=r)
{
if(a[i]<=a[j]) c[k++]=a[i++];
else c[k++]=a[j++],ans+=mid-i+1;
}
while(i<=mid)
c[k++]=a[i++];
while(j<=r)
c[k++]=a[j++];
for(int p=l;p<=r;p++)
a[p]=c[p];
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
m(1,n);
printf("%lld",ans);
return 0;
}
哪里出问题了??