#include<iostream>
using namespace std;
int num[100010], temp[100010];
long long count( int l , int r){
if(l >= r) return 0;
long long sum = 0;
int mid = (l + r) >> 1;
sum += count(l , mid);
sum += count(mid + 1 , r);
for(int i = l , j = mid + 1; i <= mid && j <= r; ){
if(num[i] > num[j]) {
sum += mid - i + 1;
j ++;
}
else i ++;
}
int i = l , j = mid + 1 , k = 0;
while(i <= mid && j <= r){
if(num[i] <= num[j]) temp[k ++] = num[i ++];
else temp[k ++] = num[j ++];
}
while(i <= mid) temp[k ++] = num[i ++];
while(j <= r) temp[k ++] = num[j ++];
for(int i = l , j = 0 ; j < k ; j ++ , i ++) num[i] = temp[j];
return sum;
}
int main(){
int n ;
cin >> n;
for(int i = 0 ; i < n ; i ++) cin >> num[i];
cout << count(0 , n - 1) << endl;
return 0;
}
标签:count,int,sum,mid,long,++,数量,逆序
From: https://www.cnblogs.com/lxy54/p/18499217