树状数组+离散化求逆序对

树状数组+离散化求逆序对

求逆序对是一个静态的问题，我们需要将静态转化为动态。即一边插入一边统计逆序对的个数。每一次把一个新的a[i]放入的时候，通过树状数组查询出已经存在的数中比它大的数的个数，并且可以肯定这些比它大的数一定是在a[i]前面的，一定构成逆序对。所以树状数组是用来统计每个数出现的次数。

两个公式

i - query(a[i]) 可以得到比a[i]大的数的个数。
query(a[i]) - mp[a[i]] 可以得到比a[i]小的个数。 这里mp[a[i]]表示离散化之后a[i]有几个。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 1e5+10;
int a[N], c[N];vector<int> v;//离散化
map<int, int> p;
int n;int query(int x)
{int res = 0;for(; x ;x -= x & (-x)) res += c[x];return res;
}void insert(int x)
{for(;x <= n;x += x&(-x)) c[x] ++;
}signed main()
{cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];v.push_back(a[i]);}// 离散化sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for(int i = 0; i < v.size(); i ++){p[v[i]] = i + 1;}int ans = 0;for(int i = 1; i <= n; i ++){insert(p[a[i]]);// 累加结果即可ans += i - query(p[a[i]]);}cout << ans << endl;return 0;
}