玄关求助 半WA半RE

P1908 逆序对

zyq13541255211 @ 2024-11-16 11:04:57

传送门

#include <bits/stdc++.h>
using namespace std;
long long L[100005],R[100005];
long long n,a[1000005],i,j,ans=0;
void MERGE(long long l,long long q,long long r){
    long long n1=q-l+1,n2=r-q;
    for(i=1;i<=n1;i++){
        L[i]=a[l+i-1];
    }
    for(j=1;j<=n2;j++){
        R[j]=a[q+j];
    }
    L[i]=0x3f3f3f3f;
    R[i]=0x3f3f3f3f;
    i=1,j=1;
    for(long long k=l;k<=r;k++){
        if(L[i]<=R[j]){
            a[k]=L[i];
            i++;
        }    
        else{
            a[k]=R[j];
            j++;
            ans+=n1-i+1;
        }
    }
    return ;
}  

void MERGE_SORT(long long l,long long r){
    if(l<r){
        long long q=(l+r)/2;
        MERGE_SORT(l,q);
        MERGE_SORT(q+1,r);
        MERGE(l,q,r);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cin>>n;
    for(long long qq=0;qq<n;qq++){
        cin>>a[qq];
    }
    MERGE_SORT(0,n-1);
    cout<<ans;
    return 0;
}

|