归并排序思路

1. 确定分界点：设 int mid = l+r>>1
2. 将区间[l,r]->[l,mid]和[mid+1,r]
3. 递归排序left和right
4. 归并——合二为一（双指针算法）✨4

从归并排序到求逆序对的转变

代码实现：

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;
const int N=1e5+10;
int q[N],tmp[N];
int n;

ll merge_sort(int l,int r)
{
    if(l>=r)return 0;

    int mid=l+r>>1;
    //res为逆序对数量
    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 //即q[i]>q[j] 此时构成了逆序对
        {
            tmp[k++]=q[j++];
            //因为为逆序对，所以该怎么统计呢？
            res = 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;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>q[i];

    cout<<merge_sort(0,n-1)<<endl;
    return 0;
}
//代码中出现的小问题记录：
/*
1. typedef long long ll;写错
2. 定义函数忘记return，在if(l>=r)return 0;中忘记return 0，我还是写成了return;
3. 对于边界问题总是出问题
*/