在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

示例 1：

**输入：**record = [9, 7, 5, 4, 6]
**输出：**8
**解释：**交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

提示：

0 <= record.length <= 50000

求逆序对的个数，就是求冒泡排序中交换的次数

同理在归并排序中我们也可以得到本应交换的次数

例如[1,3,5]和[2,4,6]合并mid=2，i=1,j=0时已经合并1下一个要放入2

如果是冒泡排序需要2分别与5，3交换

i=2,j=1时已经合并1，2，3下一个要放入4

如果是冒泡排序需要4与5交换，可以看到交换次数就是左数组剩下的数字个数，也即交换mid-i+1次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    int ans = 0;

    public : int reversePairs(vector<int> &record) {
        int n = record.size();
        vector<int> tmp(n);
        gsort(record, 0, n - 1, tmp);
        return ans;
    }
    void gsort(vector<int> &a, int l, int r, vector<int> &tmp) {
        if (l >= r)
            return;
        int mid = l + (r - l) / 2;
        gsort(a, l, mid, tmp);
        gsort(a, mid + 1, r, tmp);

        int i = l;
        int j = mid + 1;
        int tm = l;
        while (i <= mid && j <= r) {
            if (a[i] <= a[j]) {
                tmp[tm++] = a[i];
                i++;
            } else {
                tmp[tm++] = a[j];
                j++;
                ans += (mid - i + 1);
            }
        }
        while (i <= mid) {
            tmp[tm++] = a[i];
            i++;
        }
        while (j <= r) {
            tmp[tm++] = a[j];
            j++;
        }
        for (int i = l; i <= r; i++) {
            a[i] = tmp[i];
        }
    }
};