To find all the inversion pairs, we can use merge sort. That is because for a section, if we can get the inversion pair count of the left part, right part, and the count across left and right, then we can get total. So for left part and right part, we can simple do it recursively, and for the pairs across left part and right part, we compare the elements using two pointers, if q[i]>q[j], which means all the elements after q[i] in the left part should be larger than q[j], then we can add the count of all of these elements to res.
$time\ O(nlogn)$
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
int n;
LL res;
int q[N],tmp[N];
void merge_sort(int l,int r)
{
if(l>=r) return;
int mid=l+r>>1;
int i=l,j=mid+1;
int k=0;
merge_sort(l,mid);
merge_sort(mid+1,r);
while(i<=mid && j<=r)
{
if(q[i]<=q[j]) tmp[k++]=q[i++];
else
{
res+=mid-i+1;
tmp[k++]=q[j++];
}
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(i=l,k=0;i<=r;i++,k++) q[i]=tmp[k];
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>q[i];
merge_sort(0,n-1);
cout<<res;
return 0;
}