49 lines
1.0 KiB
C++
49 lines
1.0 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
typedef long long LL;
|
||
const int N = 3e5 + 10;
|
||
int n;
|
||
int q[N];
|
||
int t[N];
|
||
LL ans;
|
||
|
||
/*
|
||
6
|
||
0 1 2 3 4 5
|
||
答案：15
|
||
*/
|
||
|
||
// 归并排序，附带求顺序对的数量
|
||
void merge_sort(int q[], int l, int r) {
|
||
if (l >= r)
|
||
return;
|
||
int mid = (l + r) >> 1;
|
||
merge_sort(q, l, mid), merge_sort(q, mid + 1, r);
|
||
int i = l;
|
||
int j = mid + 1;
|
||
int k = 0;
|
||
while (i <= mid && j <= r)
|
||
if (q[i] <= q[j]) {
|
||
t[k++] = q[i++];
|
||
// 顺序对，原理：当q[i]<=q[j]时，q[i]与q[j]之后的所有数都构成顺序对
|
||
ans += r - j + 1;
|
||
} else
|
||
t[k++] = q[j++];
|
||
|
||
while (i <= mid)
|
||
t[k++] = q[i++];
|
||
while (j <= r)
|
||
t[k++] = q[j++];
|
||
for (i = l, j = 0; i <= r; i++, j++)
|
||
q[i] = t[j];
|
||
}
|
||
|
||
int main() {
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++)
|
||
cin >> q[i];
|
||
// 根据题目提示，使用归并排序，并在归并排序的过程中计算顺序对的数量
|
||
merge_sort(q, 1, n);
|
||
printf("%lld", ans);
|
||
return 0;
|
||
} |