归并排序巧解逆序对问题

逆序对归并排序模版题一.题目先简单理解下题目的意思我们要先理解何为逆序对我们输入一个n这个n数代表着这个正整数序列总共有个数像是题目所给的输出样例n6然后有5,4,2,6,3,1这六个数现在让我们判断在这个序列中有多少个逆序对我们定义俩个变量i和ji始终保持小于j如果满足这个条件的情况下ij有在i位置的数大于j位置的数即是逆序对a[i]a[j]像是i1,a[i]5,j2,a[j]4,就有ij,a[i]a[j]所以它俩就是逆序对。从题目数据上来看遍历肯定是不行的轻松超时那么这个时候就可以引入我们的归并排序的知识点了。归并排序简单来说就是拆分跟合并俩个步骤我们可以把5 4 2 6 3 1这个六个数先分为俩部分分别为5 4 2和6 3 1然后再把5 4 2分为5跟4 25 4跟2也行6 3 1分为6跟3 1接着4 2分为4跟2,3 1分为3跟1然后在倒着重新进行合并4跟2合并变为2 4,3跟1合并变为1 3然后5和2 4和进行合并2 4 5,6跟3 1合并变为1 3 6最后将2 4 5和1 3 6进行合并则变为1 2 3 4 5 6可看草稿示意图配合理解有了这样的思想那我们可以看看代码是如何实现的其实看了代码就感觉很好理解。int a[500005]{0};//存放初始序列的每个位置的值 int b[500005]{0};//充当一个拷贝数值的作用可将合并后的数值更新进a数组内 void mergesort(int l,int r)//l跟r其实就像是我们常用的sort(l,r)就是我们要排序的区间 { if(lr)return;//当lr意味着此时元素已经拆分到最小也就是拆到了只剩单个元素 int midlr1;//拆分的分界点 mergesort(l,mid);//递归调用左半部分的归并排序 mergesort(mid1,r);//递归调用右半部分归并排序 //下边开始执行时是在拆分结束后开始合并排序 int il,jmid1,kl;//k记录当前数组拷贝到了第几个i始终保持j while(imidjr)//从小到大进行排序 { if(a[i]a[j])b[k]a[i]; else { b[k]a[j]; } } while(imid)b[k]a[i];//这俩步while是上一部while后还剩余的未完成拷贝排序的补充 while(jr)b[k]a[j]; for(int il;ir;i)a[i]b[i];//将拷贝数组内的值传入原数组 }OK我们已经成功轻松的掌握了归并排序的操作那我们可以观察下归并排序函数内的操作如何进行修改或者是补充才可以对逆序对的数量进行计数while(imidjr)//我们可以借助i始终小于j的性质 { if(a[i]a[j])b[k]a[i]; else //else的触发条件其实就是a[i]a[j]而我们前面又知道i始终小于j所以每次触发我们进行一个计数即可计算出逆序对的数量 { ansmid-i1;//每次mid-i1的意思是i到mid这一区间的数都大于此时j的数(因为i到mid已经从小到大排好顺序了)且满足ij所以这一个区间都与a[j]有逆序对关系// b[k]a[j]; } }下边提供完整AC代码#includebits/stdc.h using namespace std; #define int long long #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) int a[500005]{0}; int b[500005]{0}; int ans0; void mergesort(int l,int r) { if(lr)return; int midlr1; mergesort(l,mid); mergesort(mid1,r); int il,jmid1,kl; while(imidjr) { if(a[i]a[j])b[k]a[i]; else { ansmid-i1; b[k]a[j]; } } while(imid)b[k]a[i]; while(jr)b[k]a[j]; for(int il;ir;i)a[i]b[i]; } signed main() { IOS; int n; cin n; for(int i1;in;i) { cin a[i]; } mergesort(1,n); cout ans; return 0; }