题目描述
求逆序对数量
样例
6
2 3 4 5 6 1
5
算法1
树状数组(和离散化)
时间复杂度
NlogN
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e5 + 4;
int tr[maxn];
int Rank[maxn];
int n;
ll ans;
struct node
{
int num;
int val;
}a[maxn];
bool cmp(node a, node b)
{
if (a.val == b.val)
return a.num < b.num;
return a.val < b.val;
}
int lowbit(int x)
{
return x & (-x);
}
void update(int x, int value)
{
for (; x <= n; x += lowbit(x))
{
tr[x] += value;
}
}
int query(int x)
{
int res = 0;
for (int i = x; i; i -= lowbit(i))
{
res+=tr[i];
}
return res;
}
int main()
{
cin>>n;
for (int i = 1; i <= n; i++)
{
cin >> a[i].val;
a[i].num = i;
}
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i++)
{
Rank[a[i].num] = i;
}
for (int i = 1; i <= n; i++)
{
update(Rank[i], 1);
ans += i - query(Rank[i]);
}
cout << ans << endl;
return 0;
}