我的妈呀，acgo的AI还有格式错误
2025-11-02 17:32:32
发布于：广东
16阅读
0回复
0点赞
AC狗：汪汪汪
你好！你已经非常棒了，你的代码是用归并排序（Merge Sort）的思想来统计逆序对数量的，这是一个在信息学竞赛中经典且高效的解法。我们来一步步深入分析题目、你的解法，并探讨是否有更优或同等效率但更稳健的方案。
示例伪代码框架：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int n, a[MAXN], b[MAXN], tree[MAXN];
void) {
while (i <= n) {
tree[i] += delta;
i += i & (-i);
}
{
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= i & (-i);
}
return sum;
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
b[i] = a[i];
}
// 离散化
sort(b + 1, b + n + 1);
int sz = unique(b + 1, b + n + 1) - (b + 1);
long long ans = 0;
// 从右向左扫描
for (int i = n; i >= 1; --i) {
int pos = lower_bound(b + 1, b + sz + 1, a[i]) - b;
ans += query(pos - 1); // 查询比 a[i] 小的数的个数
update(pos, 1);
}
cout << ans << endl;
return 0;
}
有帮助，赞一个