AcWing 788. 逆序对的数量

# 逆序对的数量 - 归并排序

# C++ 中 signed main 和 int main 的区别

# C 语言中 int main (int argc, char *argv []) 的两个参数的详解

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int n;
int q[N], tmp[N];

LL merge_sort(int l, int r){
    if(l >= r) return 0;
    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else{
        tmp[k++] = q[j++];
        res += mid - i + 1;
        }
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];

    for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    return res;
}

signed main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> q[i];
    
    cout << merge_sort(0, n - 1) << endl;
    
    return 0;
}

# 为什么是 mid - i + 1?

数组 a 中的 i ~ mid 的数组是递增数组， 触发条件是 a [i] > a [j]，所以 i ~ mid 中的数字都比当前 a [j] 大，所以左边 i ~ mid 的数组中有 mid - i + 1 个数比 a [j] 大

//分治思想就是把一个大问题分解成互不相关的小问题

//5 * 10^9因为会大于int的最大值 所以用longlong来存

#include <iostream>

using namespace std;

typedef long long LL;
//预处理 把下面所有LL替换成 long long

//#define 就是宏定义 typedef 就是类型的宏定义

const int N = 1e6 + 10;

int n;
int q[N], tmp[N];

LL merge_sort(int l, int r){
    if(l >= r) return 0;
    //归并排序中 这里的 >= 可以写成 == 但是快排不可以 因为快排 可能没有r r可能小于l
    
    int mid = l + r >> 1;
    //取中间值 因为这里 + 号的优先级比 >> 的优先级要高 所以可以不用加括号
    
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    
    
    //归并的过程
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else{
            tmp[k++] = q[j++];
            res += mid - i + 1;
        }
    // 扫尾
    
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    
    
    for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
    
    return res;
}

signed main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> q[i];
    
    cout << merge_sort(0, n - 1) << endl;
    
    
    return 0;
}