题解 | #逆序对#

链接//【模板】逆序对的题解

#include <bits/stdc++.h>/*我们其实学久了就知道，我们排序的过程就是消灭逆序对的过程，
 我们通过模拟归并排序，即可得出计算逆序对的方法*/ //旨在帮助大家养成动手模拟的好习惯
const int N = 5e5+10;
using namespace std;
using ll = long long;
ll a[N],n;//数组的初始化
ll b[N];//用一个数组用来存排序后的数字
ll counter = 0;//计数器
void hebin(int l,int mid,int r)//重点就是手动模拟这个过程，我们假设左右两部分已然由于，只需通过双指针大小再排序，我们发现，当右边指针q右移时，即是在排序的过程，即消灭了一定数量的逆序对，我们数一下就好了
{
    int p = l,q = mid +1;//左右指针
    for(int i = l; i <= r ;i++){
        if( (q>r)|| ( p<=mid &&a[p]<=a[q]) )//q>r的意思是右半边已经没有元素了
        {
            b[i]  = a[p];
            p++;//更新位置
        }  
        else {
            counter+=mid-p+1;//计算公式在这，我就简单说一下嘿嘿
            b[i] = a[q];
            q++;//更新位置
        }
    }
    for(int i = l;i <= r; i++){
        a[i]=b[i];
    }
}
void merge_sort(int l,int r)//归并排序的框架
{
    if(l == r)return ;//特殊情况即已经有序结束就好啦
    int mid = (l+r)/2;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    hebin(l,mid,r);//合并两块有序数组
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n;//输入数据
    for(int i = 1;i<=n;i++)cin>>a[i];
    merge_sort(1,n);
   cout<<counter;//输出
    return 0;
}