题目说明
数据范围
样例
代码
①归并排序基本思想：
②在归并的过程中，逆序对出现的三种情况：
a.全部出现在左边的区间
b.全部出现的右边的区间
c.出现在左右两个区间
黄色情况的求解方法：
找左边区间比右边区间每一个数大的个数，相加就是答案
在归并排序求出两个有序区间后，可以发现如下性质：
当qi在某一阶段大于qj，易得qi及后所有数都大于qj，也就是构成两边区间的逆序对
#include <bits/stdc++.h> using namespace std; const int N=100010; int arr[N],temp[N]; long long msort(int l,int r) { if(l>=r) return 0; //递归边界 int mid=(l+r)/2; long long res=msort(l,mid)+msort(mid+1,r); //划分区间 int i=l,j=mid+1,k=0; while(i<=mid&&j<=r) //归并过程 { if(arr[i]<=arr[j]) temp[k++]=arr[i++]; else { temp[k++]=arr[j++]; res+=mid-i+1; } } while(i<=mid) temp[k++]=arr[i++]; //扫尾 while(j<=r) temp[k++]=arr[j++]; for(int i=l,j=0;i<=r;i++,j++) //物归原主 arr[i]=temp[j]; return res; } int main() { int n; cin>>n; for(int i=0;i<n;i++) scanf("%d",&arr[i]); long long res=msort(0,n-1); cout<<res; return 0; }
