$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$
笔记：
这题与上一个题解归并排序有很大关系。
这题正解就是归并排序，当然也可以用树状数组，以后才会学到。
当每一次$b$数组中插入一个数的时候，$a$数组中已经插入的数都会比他小，因为$a$数组中所有值小于$b$数组中所有值。
那么$ans+=mid-i+1$即可。

代码：

#include <bits/stdc++.h>
using namespace std;
int n, a[100010], t[100010];
long long ans;
void merge_sort(int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l, mid); merge_sort(mid + 1, r);
    int i = l, j = mid + 1, tot = l;
    while (i <= mid && j <= r)
        if (a[i] <= a[j]) t[tot++] = a[i++];
        else t[tot++] = a[j++], ans += (long long)mid - i + 1;
    while (i <= mid) t[tot++] = a[i++];
    while (j <= r) t[tot++] = a[j++];
    for (int i = l; i <= r; i++) a[i] = t[i];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    merge_sort(1, n);
    cout << ans;
    return 0;
}