分治算法：归并排序求解逆序对 | 洛谷P1908

文章目录1.归并排序 逆序对1.1归并排序思想1.2逆序对定义1.2.1计数原理1.2.2例题1.归并排序 逆序对1.1归并排序思想主要利用分治思想 时间复杂度O(nlogn)分 对数列不断等长拆分直到一个数的长度治 回溯时 按升序合并左右两段重复以上两个过程先看下面一个例子设有数列{ 8 , 4 , 7 , 2 , 11 , 1 , 9 , 3 , 12 , 5 , 10 , 6 } \{8, 4, 7, 2, 11, 1, 9, 3, 12, 5, 10, 6\}{8,4,7,2,11,1,9,3,12,5,10,6}初始状态:{ 8 } , { 4 } , { 7 } , { 2 } , { 11 } , { 1 } , { 9 } , { 3 } , { 12 } , { 5 } , { 10 } , { 6 } \{8\}, \{4\}, \{7\}, \{2\}, \{11\}, \{1\}, \{9\}, \{3\}, \{12\}, \{5\}, \{10\}, \{6\}{8},{4},{7},{2},{11},{1},{9},{3},{12},{5},{10},{6}第一次归并后:{ 4 , 8 } , { 2 , 7 } , { 1 , 11 } , { 3 , 9 } , { 5 , 12 } , { 6 , 10 } \{4,8\}, \{2, 7\}, \{1, 11\}, \{3, 9\}, \{5, 12\}, \{6, 10\}{4,8},{2,7},{1,11},{3,9},{5,12},{6,10};第二次归并后:{ 2 , 4 , 7 , 8 } , { 1 , 3 , 9 , 11 } , { 5 , 6 , 10 , 12 } \{2, 4, 7, 8\}, \{1, 3, 9, 11\}, \{5, 6, 10, 12\}{2,4,7,8},{1,3,9,11},{5,6,10,12};第三次归并后:{ 1 , 2 , 3 , 4 , 7 , 8 , 9 , 11 } , { 5 , 6 , 10 , 12 } \{1, 2, 3, 4, 7, 8, 9, 11\}, \{5, 6, 10, 12\}{1,2,3,4,7,8,9,11},{5,6,10,12};第四次归并后:{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 } \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}{1,2,3,4,5,6,7,8,9,10,11,12}最终结果得出:{ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 } \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}{1,2,3,4,5,6,7,8,9,10,11,12}归并排序是一种稳定且高效的排序算法时间复杂度为O ( n log ⁡ 2 n ) O(n\log_2n)O(nlog2​n)1.2逆序对定义对于下标 ( i j )满足 (a[i]a[j])则 ( i , j )为一对逆序对。逆序对分为三类两个元素都在左子区间左内部逆序对两个元素都在右子区间右内部逆序对一个在左子区间、一个在右子区间跨区间逆序对核心结论每一对逆序对有且仅有一层递归会统计它任意一对逆序对 (x,y)x 在原序列位置靠左y 靠右。递归拆分过程存在唯一一层递归x 被划分到左半边y 被划分到右半边。就在这一层的合并阶段统计这一对逆序对。在更深层递归中(x,y) 会落在同一个子区间不会被拆分为左右两组因此不会重复统计。总逆序对 左内部逆序对 右内部逆序对 跨区间逆序对1.2.1计数原理递归先处理左区间、再处理右区间msort(b,mid)递归求解左内部全部逆序对msort(mid1,e)递归求解右内部全部逆序对当前层合并只统计跨左右区间的逆序对合并时左右子区间已经各自有序。当 (a[i]a[j])左区间从 i-mid 的所有元素全都大于 (a[j])一共mid‑i1个逆序对。ans mid - i 1;易错点判断条件必须是a[i] a[j]不能写a[i] a[j]。相等不是逆序对不能计数。1.2.2例题P1908 逆序对 - 洛谷//归并排序求逆序对#includebits/stdc.h#definelllonglong#defineendl\n#defineIOSios::sync_with_stdio(0),cin.tie(),cout.tie();#defineullunsignedlonglongconstll p998244353,m5e610;usingnamespacestd;ll n,a[500005],c[500005];ll ans0;voidmsort(ll b,ll e){if(be)return;ll mid(be)/2;ll ib,jmid1;ll kb;msort(b,mid);msort(mid1,e);while(imidje){if(a[i]a[j]){c[k]a[i];}else{c[k]a[j];ansmid-i1;}}while(imid){c[k]a[i];}while(je){c[k]a[j];}for(ll lb;le;l){a[l]c[l];}}intmain(){IOS cinn;for(ll i1;in;i){cina[i];}msort(1,n);coutansendl;return0;}