树状数组（2）-- 逆序对计算

题干引入

洛谷 P1908
LeedCode LCR 170

逆序数

（和线代中定义一致）在一个数字序列中，后面比前面小的数字个数之和
如 8 4 5 9 1 2 3 3 的逆序数为：6 +4 + 4+ 4+ 0+ 0+ 0 +0 = 18
使用一种办法求出逆序数

树状数组解法

根据上面序列中的数组出现次数，可以构建如下桶：

我们根据上面的表构建树状数组
当我们从原列表的后面向前面遍历，储水式num都为0，对元素 \(a_{i}\)，将其在表中的num+1，我们发现其逆序数就等于表前面小于 $a_i $ 元素的num之和。（因为是从后面遍历，如果比该元素小的且在后面的已经遍历过
因此：只需要每次加上 \(a_i\)前面之和即可

离散化

我们发现，如果序列为 1 2 100000000000000000000000 ... 就会造成构建树状数组的时候非常大，中间大量空间被浪费，因此我们先进行离散化

代码：

#include <algorithm>
#include <iostream>
using namespace std;
const int N = 5 * 10e5 + 10;
int t[N], record[N], temp[N];
int n;
void Madd(int x, int k) {
	for (; x <= n; x += x & -x) t[x] += k;
}
int Mask(int x) {
	int res = 0;
	for (; x; x -= x & -x) res += t[x];
	return res;
}
//离散化时使用sort函数用来比较的函数
bool cmp(int a, int b) {
	return a < b;
}
int main() {
	int _ = 1;
	while (_--) solve();
	return 0; 
}

solve()函数具体步骤：

void solve() {
//接受输入
	cin >> n;
	for (int i = 0; i < n; i++) cin >> record[i], temp[i] = record[i];
	//离散化
	sort(temp, temp + n, cmp);
	//lower_bound返回record[i]在temp数组中对应位置的迭代器，减去temp再加1即可获得record[i]在原数组中排序好之后的位置
	for (int i = 0; i < n; i++) record[i] = lower_bound(temp, temp + n, record[i]) - temp + 1;
	
	long long res = 0;
	for (int i = n; i > 0; i--) {
		Madd(record[i - 1], 1);
		res += Mask(record[i - 1] - 1);
	}
	cout << res << endl;
}