题目描述
题意你应该已经清楚了
废话不多说直接看Code
样例
#include"bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
int T;
int n, a[N], q[N];
ll ans;
//排序次数大于等于逆序对数 所以下面需加上等号
void merge_sort(int p[], int le, int r) {
if (le >= r)return;
int mid = le + r >> 1;
merge_sort(p, le, mid);
merge_sort(p, mid+1, r);
int i = le, j = mid + 1;
for (int k = le; k <= r; k++) {
//j>r 说明mid右边已经没有了 直接进行mid左边的操作就可以了
if (j > r || i <= mid && p[i] <= p[j])//忘了给p[i]<p[j]加上等号
q[k] = p[i++] ;
else//否则逆序了
q[k] = p[j++],ans+=mid-i+1;
}
for (int k = le; k <= r; k++)
p[k] = q[k];//最后直接赋值返回给p
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
merge_sort(a, 1, n);
cout << ans << endl;
return 0;
}