前治知识点：归并排序

题目链接：逆序对

逆序对：在一个序列中，存在一个前面的数大于后面的数就成为逆序对（如2 1 4 3 中，2 1、4 3）

用归并排序处理逆序对的时间复杂度:O(nlogn)

大致上于归并排序的模板类似，但主要的差别在于：因为归并排序分为的是左右两个区间进行处理。 所以，当左区间i所指向的元素大于右区间j指向的元素时，i与i之后的元素都与j所指向的元素成为逆序对。

如这样一个数组：

经过递归排序后

如上所说：当左区间的当前元素大于右区间的当前元素时，左区间元素与之后的元素都与右区间当前元素可以组成一个逆序对

上代码：

#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> Pall; namespace IO{ inline LL read(){ LL o=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();} return o*f; } }using namespace IO; const int N=1e6+7,INF=0x3f3f3f3f; int a[N]; 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 i=l,j=mid+1,temp[r-l+1],cnt=0; while(i<=mid&&j<=r){ if(a[i]<=a[j])temp[cnt++]=a[i++]; //其他地方如果不同，可以转移到归并排序链接。 else{//如果i指向左区间的元素大于右区间j指向的元素 res+=mid-i+1;//那么i之后的元素都能与j组成一对逆序对 temp[cnt++]=a[j++]; } } while(i<=mid)temp[cnt++]=a[i++]; while(j<=r)temp[cnt++]=a[j++]; for(i=l,j=0;i<=r;i++,j++)a[i]=temp[j]; return res; } int main(){ int n; cin>>n; for(int i=0;i<n;i++)cin>>a[i]; cout<<merge_sort(0,n-1)<<endl; return 0; }