逆序对
2024年12月25日小于 1 分钟
#include <bits/stdc++.h>
using namespace std;
int n;
int a[500000 + 5];
int temp[500000 + 5];
// 树状数组:维护 cnt[i] 存 i 出现了几次
int t[500000 + 5];
int lowbit(int x)
{
return x & -x;
}
void update(int x, int y)
{
for (int i = x; i <= n; i += lowbit(i))
t[i] += y;
}
int query(int x)
{
int res = 0;
for (int i = x; i >= 1; i -= lowbit(i))
res += t[i];
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
// 离散化
for (int i = 1; i <= n; i++)
temp[i] = a[i];
sort(temp + 1, temp + n + 1);
int tot = unique(temp + 1, temp + n + 1) - temp - 1;
for (int i = 1; i <= n; i++)
a[i] = lower_bound(temp + 1, temp + tot + 1, a[i]) - temp;
// 逆序对
long long ans = 0;
for (int i = 1; i <= n; i++)
{
// 检查多少组 a[<i] ~ a[i] 逆序对
// 检查 a[1]~a[i-1] 有几个大于 a[i] 的数
// 检查 cnt[a[i]+1]~cnt[n] 和为多少
ans += query(n) - query(a[i]);
update(a[i], 1);
}
cout << ans;
return 0;
}