找了半天都没找到哪里错了，我太菜了

Man_CCNU @ 2022-05-26 09:50:00

#include<iostream>

using namespace std;

const int N = 5e6 + 10;
int a[N], n;
long long int res;

void mergesort(int l, int r)
{
    if (r <= l) return;
    int mid = (l + r) / 2;
    mergesort(l, mid);
    mergesort(mid + 1, r);
    int tem[N], tem2[N];

    for (int i = 1; i <= mid - l + 1; i++) {
        tem[i] = a[i + l - 1];
    }
    for (int i = 1; i <= r - mid; i++) {
        tem2[i] = a[i + mid];
    }

    int ptr1 = 1, ptr2 = 1, cur = l;
    while (ptr1 <= mid - l + 1 && ptr2 <= r - mid) {
        if (tem[ptr1] <= tem2[ptr2]) {
            a[cur++] = tem[ptr1++];
        }
        else {
            a[cur++] = tem2[ptr2++];
            res = res + mid - ptr1 + 1;
        }
    }
    while (ptr1 <= mid - l + 1) {
        a[cur++] = tem[ptr1++];
    }
    while (ptr2 <= r - mid) {
        a[cur++] = tem2[ptr2++];
    }

    return;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    mergesort(1, n);
    cout << res << endl;

    return 0;
}

by 昒昕 @ 2022-05-26 13:21:20

@Man_CCNU 这样例都没过啊

by 昒昕 @ 2022-05-26 13:29:14

@Man_CCNU

#include<iostream>

using namespace std;

const int N = 5e6 + 10;
int a[N],tem[N],n;
long long res;

void mergesort(int l, int r)
{
    if (r <= l) return;
    int mid = (l + r) / 2;
    mergesort(l, mid);
    mergesort(mid + 1, r);

    int ptr1 = l, ptr2 = mid + 1, cur = l;
    while (ptr1 <= mid && ptr2 <= r) {
        if (a[ptr1] <= a[ptr2]) {
            tem[cur++] = a[ptr1++];
        }
        else {
            tem[cur++] = a[ptr2++];
            res = res + mid - ptr1 + 1;
        }
    }
    while (ptr1 <= mid) {
        tem[cur++] = a[ptr1++];
    }
    while (ptr2 <= r) {
        tem[cur++] = a[ptr2++];
    }
    for (int i=l;i<=r;i++) a[i]=tem[i];
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    mergesort(1, n);
    cout << res << endl;

    return 0;
}

by Man_CCNU @ 2022-05-26 15:05:56

#include<iostream>

using namespace std;

const int N = 1e6 + 10;
int a[N], n;
long long int res;
int tem[N], tem2[N];

void mergesort(int l, int r)
{
    if (r <= l) return;
    int mid = (l + r) / 2;
    mergesort(l, mid);
    mergesort(mid + 1, r);

    for (int i = 1; i <= mid - l + 1; i++) {
        tem[i] = a[l + i - 1];
    }
    for (int i = 1; i <= r - mid; i++) {
        tem2[i] = a[mid + i];
    }
    int i = 1, j = 1, cur = l;
    while (i <= mid - l + 1 && j <= r - mid) {
        if (tem[i] <= tem2[j]) {
            a[cur++] = tem[i++];
        }
        else {
            res = res + mid - (i+l-1)+1;
            a[cur++] = tem2[j++];
        }
    }
    while (i <= mid - l + 1) {
        a[cur++] = tem[i++];
    }
    while (j <= r - mid) {
        a[cur++] = tem2[j++];
    }

    return;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    mergesort(1, n);
    cout << res << endl;

    return 0;
}

by Man_CCNU @ 2022-05-26 15:06:25

找到错了，计算时下标搞错了

by Man_CCNU @ 2022-05-26 15:07:07

@昒昕 谢谢！