题干引入
洛谷 P1908
LeedCode LCR 170
逆序数
（和线代中定义一致）在一个数字序列中，后面比前面小的数字个数之和
如 8 4 5 9 1 2 3 3 的逆序数为：6 +4 + 4+ 4+ 0+ 0+ 0 +0 = 18
使用一种办法求出逆序数
树状数组解法
根据上面序列中的数组出现次数，可以构建如下桶：
| ID | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| num | 1 | 1 | 2 | 1 | 1 | 0 | 0 | 1 | 1 |
我们根据上面的表构建树状数组
当我们从原列表的后面向前面遍历，储水式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;
}