@[52hertz_yh](/user/1269776) 使用指令集优化即可。
by 0x3F @ 2024-04-16 13:43:42
@[0x3F](/user/153422) 详细一点可以吗?
感谢
by 52hertz_yh @ 2024-04-16 13:51:00
@[52hertz_yh](/user/1269776) 用归并排序或者树状数组。
by Weekoder @ 2024-04-16 13:58:01
@[52hertz_yh](/user/1269776) 建议重构代码,$O(n^2)$ 一般卡不过
by d909RCA @ 2024-04-16 14:08:01
@[52hertz_yh](/user/1269776) 线段树
by luuia @ 2024-04-16 14:25:56
@[Weekoder](/user/800884) 可以用归并吗?
怎么用呀?
感谢指导
by 52hertz_yh @ 2024-04-17 12:46:16
@[52hertz_yh](/user/1269776) 可以参考一下我的代码,只要在归并排序内部计数即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int n, a[N], b[N];
ll ans;
void merge(int l, int r) {
int mid = l + r >> 1;
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j])
b[k++] = a[i++];
else
b[k++] = a[j++], ans += mid - i + 1;
}
while (i <= mid) b[k++] = a[i++];
while (j <= r) b[k++] = a[j++];
for (int i = l; i <= r; i++) a[i] = b[i];
}
void MergeSort(int arr[], int l, int r) {
if (l >= r) return ;
int mid = l + r >> 1;
MergeSort(arr, l, mid);
MergeSort(arr, mid + 1, r);
merge(l, r);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
MergeSort(a, 1, n);
cout << ans;
return 0;
}
```
by Weekoder @ 2024-04-17 13:14:53
这是较为简单的方法。
by Weekoder @ 2024-04-17 13:15:15