目录
前置知识
概述
思路
算法过程
复杂度
Code
前置知识
在本篇文章之前，你应该先掌握归并排序的基本技巧，详见：「数组」归并排序 / if语句优化|小区间插入优化（C++）
概述
LeetCode LCR 076：
在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。
示例 :
输入：record = [9, 7, 5, 4, 6] 输出：8 解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
逆序对问题是归并排序的DLC问题。
逆序对(nums[i],nums[j])的定义是：nums[i]>nums[j]且0<=i<j<=n。
我们希望求解一个数组的全部逆序对，暴力做法似乎很直观，但是时间复杂度相当糟糕，是O(n²)级别的。
但是归并排序提供给我们一种手段，在nlogn时间内解决这个问题。
思路
归并排序由两部分组成：递归和合并。
合并是由二路合并实现的，这给了我们一点提示。
回想这段代码：
void merge_if(int arr[], int l, int m, int r, int assist[]) {if (arr[m - 1] <= arr[m])return;memcpy(&assist[l], &arr[l], sizeof(int) * (r - l));int i, j, k;for (i = l, j = m, k = l;; k++) {if (i == m || j == r)break;if (assist[i] <= assist[j])arr[k] = assist[i++];else arr[k] = assist[j++];}while (i != m)arr[k++] = assist[i++];while (j != r)arr[k++] = assist[j++];
}我们不妨称[l,m)为左路，[m,r)为右路，他们交错形成合并路。
左路元素在原数组中的下标一定小于右路元素，那怎么找逆序对呢？
注意到：合并操作总是依靠比大小实现。这意味着：
左路元素加入到合并路时，在它前面加入到合并路的右路元素一定可以与之构成逆序对。
至于一路内部的逆序对？那是由上一级合并操作计算得到的。
算法过程
每次向合并路加入左路元素时，计算它之前有多少右路元素被加入到合并路即可。
依靠mark储存一开始右路索引j的位置，此后每次加入左路元素，ans+=j-mark；
稍改上面的代码，我们就得到了：
void merge_if(int arr[], int l, int m, int r, int assist[]) {if (arr[m - 1] <= arr[m])return;memcpy(&assist[l], &arr[l], sizeof(int) * (r - l));int i, j, k, mark = m;for (i = l, j = m, k = l;; k++) {if (i == m || j == r)break;if (assist[i] <= assist[j])arr[k] = assist[i++],ans += j-mark;else arr[k] = assist[j++];}while (i != m)arr[k++] = assist[i++],ans += j-mark;while (j != r)arr[k++] = assist[j++];
}复杂度
时间复杂度：O(nlogn)
空间复杂度：O(n)
复杂度分析详见：「数组」归并排序 / if语句优化|小区间插入优化（C++）
Code
class Solution {
private:
int ans=0;
void merge_if(int arr[], int l, int m, int r, int assist[]) {if (arr[m - 1] <= arr[m])return;memcpy(&assist[l], &arr[l], sizeof(int) * (r - l));int i, j, k,mark=m;for (i = l, j = m, k = l;; k++) {if (i == m || j == r)break;if (assist[i] <= assist[j])arr[k] = assist[i++],ans+=j-mark;else arr[k] = assist[j++];}while (i != m)arr[k++] = assist[i++],ans+=j-mark;while (j != r)arr[k++] = assist[j++];
}
void recursion(int arr[], int l, int r, int assist[]) {if (r - l <= 1)return;int m = (l + r) / 2;recursion(arr, l, m, assist);recursion(arr, m, r, assist);merge_if(arr, l, m, r, assist);
}
void MGsort(int arr[], int len) {int* assist = new int[len];recursion(arr, 0, len, assist);delete[] assist;
}
public:int reversePairs(vector<int>& record) {MGsort(record.data(),record.size());return ans;}
};