题目大意
求解逆序对数量
解题思路
树状数组加离散化
步骤见树状数组专题
具体代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int n, m;
int a[N], b[N], c[N];
int find(int x) //返回a[i]在b数组中的下标
{
int l = 1, r = m;
while (l < r)
{
int mid = l + r >> 1;
if (b[mid] >= x)
r = mid;
else
l = mid + 1;
}
return l;
}
void add(int x, int t)
{
for (; x <= n; x += x & -x)
c[x] += t;
}
LL query(int x)
{
LL res = 0;
for (; x; x -= x & -x)
res += c[x];
return res;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
b[i] = a[i];
}
sort(b + 1, b + n + 1);
m = 1;
for (int i = 2; i <= n; i++) //去重
if (b[i] != b[m])
b[++m] = b[i];
LL ans = 0;
for (int i = n; i; i--)
{
int t = find(a[i]);
ans += query(t - 1);
add(t, 1);
}
cout<<ans<<'\n';
return 0;
}