30求调

cgxd @ 2024-06-05 21:51:23

#include<bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
int n, ans;
vector<int> v1, v2;
void merge(int l, int r){
    int p1 = l, mid = l + r >> 1, p2 = mid + 1;
    v2.resize(p1);
    while(p1 <= mid and p2 <= r){
        if(v1[p1] < v1[p2])
            v2.push_back(v1[p1++]);
        else{
            v2.push_back(v1[p2++]);
            ans += mid - p1 + 1;
        }
    }while(p1 <= mid)
        v2.push_back(v1[p1++]);
    while(p2 <= r)
        v2.push_back(v1[p2++]);
    for(reg int i = l; i <= r; ++i)
        v1[i] = v2[i];
}void merge_sort(int l, int r){
    if(l >= r)
        return;
    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    merge(l, r);
}signed main(){
    cin >> n;
    for(reg int i = 0; i < n; ++i){
        reg int k;
        scanf("%lld", &k);
        v1.push_back(k);
    }merge_sort(0, n - 1);
    cout << ans;
    return 0;
}

by wuhaoran2012 @ 2024-07-20 17:51:36

@cgxd

#include<bits/stdc++.h>
#define reg register
#define int long long
using namespace std;
int n, ans;
vector<int> v1, v2;
void merge(int l, int r){
    int p1 = l, mid = (l + r) >> 1, p2 = mid + 1;
    v2.clear();
    while(p1 <= mid and p2 <= r){
        if(v1[p1] <= v1[p2])//将小于改成小于等于，因为等于不会增加逆序对
            v2.push_back(v1[p1++]);
        else{
            v2.push_back(v1[p2++]);
            ans += mid - p1 + 1;
        }
    }
    while(p1 <= mid)
        v2.push_back(v1[p1++]);
    while(p2 <= r)
        v2.push_back(v1[p2++]);
    for(reg int i = l; i <= r; ++i)
        v1[i] = v2[i-l];
}void merge_sort(int l, int r){
    if(l >= r)
        return;
    int mid = (l + r) >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);
    merge(l, r);
}signed main(){
    cin >> n;
    for(reg int i = 0; i < n; ++i){
        reg int k;
        scanf("%lld", &k);
        v1.push_back(k);
    }
    merge_sort(0, n - 1);
    cout << ans;
    return 0;
}

by cgxd @ 2024-07-20 18:25:35

已过，感谢