AcWing 788. 逆序对的数量
原题链接
简单
作者:
虚实相依
,
2024-03-25 23:14:04
,
所有人可见
,
阅读 2
#include<iostream>
#include<cstring>
using namespace std;
#define LL long long
const int N = 100005;
int n;
int p[N];
int tem[N];
LL merge_sort(int l, int r)
{
if (l >= r) return 0;
int mid = l + r >> 1;
LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);//1.已经实现了子数组的升序排列
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r) {
if (p[i] <= p[j]) tem[k++] = p[i++];
else
{
tem[k++] = p[j++];
res += mid-i + 1;//2.两边数组已经是升序的,如果p[i]>p[j],i到mid的元素和p[j]都形成逆序对
}
}
while (i <= mid) tem[k++] = p[i++];
while (j <= r) tem[k++] = p[j++];
for (int i = l, j = 0; i <= r; i++, j++) p[i] = tem[j];
return res;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> p[i];
cout << merge_sort(1, n)<< ' ';
return 0;
}