RE了

P1908 逆序对

Paris_Commune @ 2022-03-30 19:40:52

#include<iostream>
using namespace std;
long long n,a[500005],d[500005],ans=0;
void merge(int s,int t){
    if(s==t)return;
    int mid=(s+t)/2,i=s,j=mid+1,k=s;
    merge(s,mid);
    merge(mid+1,t);
    for(i=s;i<=mid;i++){
        while((a[j]<a[i])&&(j<=t))j++;
        ans=ans+(j-mid-1);
    }
    i=s;j=mid+1;
    while(i<=mid&&j<=t){
        if(a[i]<a[j])
        d[k++]=a[i++];
        else d[k++]=a[j++];
    }
    while(i<=mid)
    d[k++]=a[j++];
    while(j<=t)
    d[k++]=a[j++];
    for(int r=s;r<=t;r++){
        a[r]=d[r];
    }
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    merge(1,n);
    cout<<ans;
    return 0;
 }

|