提交时间:2024-03-26 14:46:15
运行 ID: 139871
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll sum_nixu; ll a[500010]; ll n; ll t[500010]; void merge_sort(ll a[],ll l,ll r) { if(l==r) { return ; } ll mid=(l+r)/2; merge_sort(a,l,mid); merge_sort(a,mid+1,r); for(ll i=l,j=mid+1,k=l;k<=r;k++) { if(i==mid+1) { t[k]=a[j]; j++; } else if(j==r+1) { t[k]=a[i]; i++; } else { if(a[i]<=a[j]) { t[k]=a[i]; i++; } else { sum_nixu=sum_nixu+(mid-i+1); t[k]=a[j]; j++; } } } for(ll i=l;i<=r;i++) { a[i]=t[i]; } return ; } int main() { scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } merge_sort(a,1,n); printf("%lld",sum_nixu); return 0; }