56 lines
1.1 KiB
C++
56 lines
1.1 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
using namespace std;
|
|
//归并的时候 如果交换顺序逆序对++
|
|
long long ans = 0;
|
|
void merge(vector<int>& arr, int l, int r){
|
|
int mid = l + (r-l)/2;
|
|
vector<int> tmp;
|
|
int i = l, j = mid+1;
|
|
while(i <= mid && j <= r){
|
|
if(arr[i] <= arr[j]){
|
|
tmp.push_back(arr[i]);
|
|
i++;
|
|
} else {
|
|
tmp.push_back(arr[j]);
|
|
j++;
|
|
ans += mid-i+1;
|
|
}
|
|
}
|
|
while (i <= mid) {
|
|
tmp.push_back(arr[i]);
|
|
i++;
|
|
}
|
|
while (j <= r) {
|
|
tmp.push_back(arr[j]);
|
|
j++;
|
|
}
|
|
for(int i = l; i <= r; i++){
|
|
arr[i] = tmp[i-l];
|
|
}
|
|
}
|
|
void mergesort(vector<int>& arr, int l, int r){
|
|
if(l >= r) return;
|
|
int mid = l + (r-l)/2;
|
|
mergesort(arr, l, mid);
|
|
mergesort(arr, mid+1, r);
|
|
|
|
merge(arr, l, r);
|
|
}
|
|
//辅助函数
|
|
|
|
int main(){
|
|
int n;
|
|
cin >> n;
|
|
vector<int> arr(n);
|
|
for(int i = 0; i < n; ++i){
|
|
cin >> arr[i];
|
|
}
|
|
mergesort(arr,0, arr.size()-1);
|
|
/*for(auto x: arr){
|
|
cout << x << " ";
|
|
} cout << endl;*/
|
|
cout << ans << endl;
|
|
return 0;
|
|
}
|