01_归并排序 merge_sort

递归:

1）终止条件
2）本级递归（通用）需要做什么
3）返回值

注: 不要纠结每一级的细节，认真就输了

选择排序是从全局到局部，递归语句放在最后
归并排序是从局部到全局，递归语句放在前面

#include <iostream>

using namespace std;

const int N = 100010;
int n, a[N], tmp[N];

void merge_sort(int a[], int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;

    /*
    若用 merge_sort(a, l, mid - 1), merge_sort(a, mid, r);
        则需让 mid 向上取整: l + r + 1 >> 1，还要记得改下面 i 和 j 的取值和判断条件；
        此时 mid 不能向下取整，否则 mid 可能取到 l，造成无限划分
        例: 若只有两个元素 {a, b}，则 merge_sort(mid, r) 会造成无限划分
    */
    merge_sort(a, l, mid), merge_sort(a, mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];

    /*
    为什么 i 不从 0 开始，而 j 从 0 开始: (用 i&j 是因为不想定义新变量，反正上面排序每次会再初始化)
        j 从 0 开始: 因为上面 tmp 的下标 k 总是从 0 开始，存储局部被排好的元素；
        i 从 0 开始: 每次局部的元素被排好之后 原数组a 要存储（覆盖）与之对应位置 (区间(l, r)) 的元素，
                     但是如果每次都从下标 0 开始存，原数组 a 中不应该被改动的位置会被 tmp 覆盖，
                     有些元素可能就被覆盖没了 (存储的位置不对)
    */
    for (i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    merge_sort(a, 0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";

    return 0;
}

02_逆序对的数量 reverse_ pair_number

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 100010;
int n, a[N], tmp[N];
LL ans;

LL merge_reverse(int a[], int l, int r) {
    if (l >= r) return ans;

    int mid = l + r >> 1;
    merge_reverse(a, l, mid), merge_reverse(a, mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++], ans += mid - i + 1;
        /* 
        左边有序，只要有左数 > 右数，则左区间中左数及其后面的数都会 > 该右数，
        只需把该左数到左区间末端的数的数量加上即可;
        每一层的 ans 都会累加当前递归层级的逆序对数量

        统计先于排序，每次统计的逆序对都基于局部的无序状态，
        然后合并当前区间变有序，此时不会影响已经统计的结果
        */
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];

    for (i = l, j = 0; i <= r; i++, j++) a[i] = tmp[j];

    return ans; // 返回前面每级递归累加的逆序对总个数
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << merge_reverse(a, 0, n - 1) << endl;

    return 0;
}