只有逆序对才需要换

#include<bits/stdc++.h>
#define memset(a) memset(a,0,sizeof(a))
using namespace std;
int n;
long long ans=0;
int a[500005],b[500005];
void merge(int l,int r){
    if(l==r){
        return;
    }else if(l==r-1){
        if(a[l]>a[r]){
            swap(a[l],a[r]);
            ans++;
        }
        return;
    }
    int mid=(l+r)>>1;
    merge(l,mid);
    merge(mid+1,r);
    int k=l,i,j;
    for(i=l,j=mid+1;i<=mid&&j<=r;){
        if(a[i]>a[j]){
            b[k++]=a[j++];
            ans+=mid-i+1;
        }else{
            b[k++]=a[i++];
        }
    }
    for(;i<=mid;){
        b[k++]=a[i++];
    }
    for(;j<=r;){
        b[k++]=a[j++];
    }
    for(int i=l;i<=r;i++){
        a[i]=b[i];
    }
    return;
}
int main()
{
    while(cin>>n){
        if(n==0)break;
        memset(a);
        memset(b);
        ans=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        merge(1,n);
        cout<<ans<<endl;
    }
}