归并分治#

归并分治算法用于解决有以下特征的问题：

整个问题的答案 = 左部分答案 + 右部分答案 + 跨越左右产生的答案
计算“跨越左右产生的答案”时，左右各有序是否可以方便问题解决

在第一个特征中，“跨越左右产生的答案”和merge过程相关，往往一个问题被分解到最小部分的时候，左部分与右部分的答案是0，这时候的答案完全来源于merge过程

而对于第二个特征，左右各有序可以帮助我们使用双指针比较数组的两个部分。通过比较两个数组之间的数据的关系，将两部分有序地写入辅助数组中，这个过程中往往会产出题目所需的答案

小和问题#

题目：牛客🔗

数组小和的定义如下：

\sum^n_{i=1} f_i

其中 $f_i$ 的定义是第 i 个数的左侧小于等于 $s_i$ 的个数

例如，数组 s = [1, 3, 5, 2, 4, 6] ，在 s[0] 的左边小于或等于 s[0] 的数的和为 0 ；在 s[1] 的左边小于或等于 s[1] 的数的和为 1 ；在 s[2] 的左边小于或等于 s[2] 的数的和为 1+3=4 ；在 s[3] 的左边小于或等于 s[3] 的数的和为 1 ；

在 s[4] 的左边小于或等于 s[4] 的数的和为 1+3+2=6 ；在 s[5] 的左边小于或等于 s[5] 的数的和为 1+3+5+2+4=15 。所以 s 的小和为 0+1+4+1+6+15=27

给定一个数组 s ，实现函数返回 s 的小和

数据范围： $0 < n \leq 10^5$ ， $|s_i| \leq 100$

实例1

1
input: [1,3,5,2,4,6]
2
output: 27

实例2

1
input: [1]
2
output: 0

题目分析#

做了归并分治的题目我发现，使用归并分治解决的问题，往往会出现左侧，右侧这样的字眼。而且不是左侧几个，而且左侧的所有元素。

这题既然提到了“左侧”，那么我们不妨从数组的左侧开始看起，考虑数组s，0位置上为1，左侧没有数字，因此不加，1位置上为3，左侧为1，那么ans += s[0]，2位置上为5，那么ans+=s[0] + s[1]。

我们观察到，当2位置的数字被“加入”到我们考虑的范围的时候，我们会遍历0,1位置上的数，看是否满足“小于等于”的条件。

如果将前三个位置的数字开始划分，上述的过程就可以描述成当s[0]与s[1]进行merge之后，s[:1]与s[2]的进行merge的过程。进而我们可以考虑s[:1]与s[2:3]merge会是一个什么样的过程。基于归并分治的特征，我们可以先假设s[2:3]有序，此时的数组为s = [1,3,2,5]，那么有序的数组是否会带来及一些计算的遍历？我们发现，如果这两边都是有序的，那么通过左右两个指针指向数组的两边的时候，当我确定s[0] < s[2]的时候，当右指针来到s[3]的时候，我不需要将左指针指向左侧数组的头，而只需要加上s[1]的累计值即可。

到这儿我们基本上确定了这个问题确实可以通过归并分治进行求解。那么我们应该考虑的就是merge过程中，如何移动左右两个指针。根据问题描述，我们知道，数组小和取决于右侧比左侧大的值，那么我们就知道需要优先移动右侧的值，根据右侧的值来确定左侧值。

题解代码#

1
using ll = long long;
2

3
class Solution {
4

5
private:
6
  ll merge(vector<int> &nums, int l, int m, int r) {
7
    if (l == r)
8
      return 0L;
9
    ll res = 0L;
10
    auto lp = nums.begin() + l;
11
    ll lp_sum = 0L;
12

13
    for (auto rp = nums.begin() + m + 1; rp != nums.begin() + r + 1; rp++) {
14
        for (;lp != nums.begin() + m + 1;) {
15
            if (*lp > *rp)  break;
16
            lp_sum += *lp;
17
            lp++;
18
        }
19

20
        res += lp_sum;
21
    }
22
    sort(nums.begin() + l, nums.begin() + r + 1);
23
    return res;
24
  }
25

26
  ll mergeCal(vector<int> &nums, int l, int r) {
27
    if (l >= r)
28
      return 0L;
29

30
    int m = (l + r) >> 1;
31
    // cout << m << " ";
32
    ll res =
33
        mergeCal(nums, l, m) + mergeCal(nums, m + 1, r) + merge(nums, l, m, r);
34
    return res;
35
  }
36

37
public:
38
  /**
39
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
40
   *
41
   *
42
   * @param nums int整型vector
43
   * @return long长整型
44
   */
45
  long long calArray(vector<int> &nums) {
46
    ll res = mergeCal(nums, 0, nums.size() - 1);
47
    return res;
48
  }
49
};

CAUTION
其实上述的代码是有问题的。在merge的过程中，如果我们需要减少复杂度，那么就应该使用辅助数组在移动指针的同时进行这部分数组的排序，而不是排序之后使用sort在原数组上直接进行排序。这样虽然降低了空间复杂度，但却牺牲了时间复杂度

翻转和#

原题链接：力扣🔗

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1] 输出: 2

示例 2:

输入: [2,4,3,5,1] 输出: 3

注意:

给定数组的长度不会超过50000。
输入数组中的所有数字都在32位整数的表示范围内。

题目分析#

我们依旧先考虑在完成nums[0:1]之后，如何获得nums[0:2]的答案。就是看左侧有多少能大于两倍右侧数。大于两倍右侧数的数量显然是可以通过nums[0:1]有序快速得到的。

考虑nums[0:1]与nums[2:3]，如果nums[2]已经小于2 * nums[0]了，那么在nums[2:3]有序的条件下，nums[3]一定满足条件。这也是可以使用归并分治解决的问题。

题解代码#

1
class Solution {
2
public:
3
  int merge(vector<int> &nums, int l, int m, int r) {
4
    int lp = l;
5
    int rp = m + 1;
6
    int rp_min = m + 1;
7
    int ans = 0;
8

9
    for (; lp <= m; lp++) {
10
      for (rp = rp_min; rp <= r; rp++) {
11
        long long tmp = 2L * nums[rp];
12
        tmp -= nums[lp];
13
        if (tmp < 0L) {
14
          rp_min++;
15
        } else {
16
          break;
17
        }
18
      }
19
      ans += rp_min - m - 1;
20
    }
21

22
    sort(nums.begin() + l, nums.begin() + r + 1);
23
    return ans;
24
  }
25

26
  void divide(vector<int> &nums, int &res, int l, int r) {
27
    if (l >= r)
28
      return;
29

30
    int m = (l + r) >> 1;
31
    divide(nums, res, l, m);
32
    divide(nums, res, m + 1, r);
33
    res += merge(nums, l, m, r);
34
  }
35

36
  int reversePairs(vector<int> &nums) {
37
    int res = 0;
38
    divide(nums, res, 0, nums.size() - 1);
39

40
    return res;
41
  }
42
};