ACWing Prime Algorithm

逆序对的数量

给定一个长度为 \(n\) 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 \(i\) 个和第 \(j\) 个元素，如果满足 \(i<j\) 且 \(a[i]>a[j]\)，则其为一个逆序对；否则不是。

输入格式

第一行包含整数 \(n\)，表示数列的长度。

第二行包含 \(n\) 个整数，表示整个数列。

输出格式

输出一个整数，表示逆序对的个数。

数据范围

\(1≤n≤100000\)，数列中的元素的取值范围 \([1,109]\)。

输入样例：

6
2 3 4 5 6 1

输出样例：

5

Code

240204

#include<bits/stdc++.h>
using namespace std;
long long cnt=0;
int tmp[100010];
void reverse_order_pair(vector<int>& v,int l,int r){
    if(l>=r)    return;
    int mid=(l+r)/2;
    reverse_order_pair(v,l,mid);
    reverse_order_pair(v,mid+1,r);
    // cout<<"l->mid:";
    // for(int k=l;k<=mid;k++) cout<<" "<<v[k];
    // cout<<endl<<"mid+1->r:";
    // for(int k=mid+1;k<=r;k++)   cout<<" "<<v[k];
    // cout<<endl<<"cnt= "<<cnt;
    int k=0,i=l,j=mid+1;
    while(i<=mid && j<=r){
        if(v[i]<=v[j]){
            tmp[k++]=v[i++];
        }
        else{
            tmp[k++]=v[j++];
            cnt+=mid-i+1;
            // cnt++;
        }
    }
    while(i<=mid){
        tmp[k++]=v[i++];
        // cnt+=mid-i+1;
    }
    while(j<=r){
        tmp[k++]=v[j++];
        // cnt++;
    }
    for(i=l,j=0;i<=r;i++,j++)   v[i]=tmp[j];
    // cout<<"->"<<cnt<<endl<<endl;
}
int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    reverse_order_pair(v,0,n-1);
    cout<<cnt<<endl;
    return 0;
}