归并排序有什么问题吗

P1908 逆序对

Chtholly_is_cute @ 2024-07-13 14:55:26

0pts的code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
long long ans=0;
int n,a[114514*5],b[114514*5];
void msort(int l,int r);
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    msort(1,n);
    cout<<ans<<endl;
    return 0;
}
void msort(int l,int r){
    if(l==r)return;
    int mid=(l+r)/2;
    int i=l,j=mid+1,k=r;
    msort(l,mid);
    msort(mid+1,r);
    while(i<=mid&&j<=r){
        if(a[i]<=a[j])b[k++]=a[i++];
        else b[k++]=a[j++],ans+=mid-i+1;
    }
    while(i<=mid)b[k++]=a[i++];
    while(j<=r)b[k++]=a[j++];
    for(int x=l;x<=r;x++)a[x]=b[x];
}

by o7u7o @ 2024-07-13 15:17:14

```cpp int i=l,j=mid+1,k=r; 改为 int i=l,j=mid+1,k=l; ```

by liaoxingrui @ 2024-07-15 08:51:27

@Chtholly_is_cute

k = r$ 改为 $k = l

|