手写归并

 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
43
44
45
46
47
48
49

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void merge_range(i64 *arr, int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    vector<i64> tmp(right + 1, 0);
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    while (i <= mid)    tmp[k++] = arr[i++];
    while (j <= right)  tmp[k++] = arr[j++];
    // 回写到原数组
    for (int p = left; p <= right; ++p) {
        arr[p] = tmp[p];
    }
}


void merge_sort(i64 *arr, int left, int right) {
    if (left >= right) return;  
    int mid = left + (right - left) / 2;
    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);
    merge_range(arr, left, mid, right);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<i64> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    merge_sort(a.data(), 1, n);

    for (int i = 1; i <= n; ++i) {
        cout << a[i] << " \n"[i == n];
    }
    return 0;
}

 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

// 合并两个有序子数组 [left..mid] 和 [mid+1..right]，
// 返回此步骤中的逆序对数
i64 merge_count(i64 *arr, i64 left, i64 mid, i64 right, vector<i64> &temp) {
    i64 inv = 0;                       // 本次合并的逆序计数
    i64 i = left, j = mid + 1, k = left;
    // 两路归并，统计跨段逆序
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            // 正确的逆序计数公式
            inv += (mid - i + 1);      // 剩余左段元素均与 arr[j] 构成逆序&#8203;:contentReference[oaicite:2]{index=2}
        }
    }
    // 复制剩余部分
    while (i <= mid)    temp[k++] = arr[i++];
    while (j <= right)  temp[k++] = arr[j++];
    // 一次性回写原数组
    for (i64 p = left; p <= right; ++p) {
        arr[p] = temp[p];
    }
    return inv;
}

// 递归归并排序并统计逆序对
i64 merge_sort_count(i64 *arr, i64 left, i64 right, vector<i64> &temp) {
    if (left >= right) return 0;       // 基准情况：区间为空或仅一个元素&#8203;:contentReference[oaicite:3]{index=3}
    i64 mid = left + (right - left) / 2;
    i64 inv = 0;
    inv += merge_sort_count(arr, left, mid, temp);
    inv += merge_sort_count(arr, mid + 1, right, temp);
    inv += merge_count(arr, left, mid, right, temp);
    return inv;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n;
    cin >> n;
    vector<i64> nums(n + 1), temp(n + 1);
    for (i64 i = 1; i <= n; ++i) {
        cin >> nums[i];
    }

    // 将 ans 局部化，避免多组测试时结果累加&#8203;:contentReference[oaicite:4]{index=4}
    i64 ans = merge_sort_count(nums.data(), 1, n, temp);
    cout << ans << "\n";

    return 0;
}