[AcWing 788]逆序对的数量

#include<iostream>
using namespace std;

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

typedef long long LL; //最坏情况下逆序数为n*(n-1)/2  结果值会爆int 

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; //将q[j]放入tmp[k]时 在总数中加上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; //逆序数
}

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


/*
归并排序基本流程：
1. 将整个区间一分为二
[L,R] --> [L,mid],[mid+1,R]
2.递归排序两个子区间  
[L,mid]和[mid+1,R]
3.归并，将左右两个有序序列合并为一个有序序列


求逆序数，分三种情况：
1.全部都在左半边的情况(左半边内部的逆序对的数量）
 merge_sort(L,mid)
2.全部都在右半边的情况 (右半边内部的逆序对的数量）
 merge_sort(mid+1,R)
3.左边一个数，右边一个数的情况(归并的过程）
左边已有序 且 右边已有序
双指针i和j
 L : |--------------------------|
     l          i ------------->mid
 R : |--------------------------|
                       j
                       Sj = mid-i+1
tmp: |------
           k
q[i]和q[j]做比较，二者中较小的数放入tmp[k]，指针后移
当q[i] > q[j]时，L中比q[j]大的数的个数为Sj=从i开始到mid的数的个数= mid-i+1
每次要把q[j]输出来时（即每次要把q[j]放入tmp[k]时），在答案（即逆序数总数）中加上一个mid-i+1 
*/