二路归并、逆序对 多路归并，堆栈
1、多路归并模板
先将数据读入堆栈，然后取栈顶的最大值或最小值，最后再根据公式进行递推求出需要添加的元素。
题目：
https://www.acwing.com/problem/content/description/1264/
https://www.acwing.com/problem/content/148/
模板：
int work(int ni,int dt){ priority_queue<PII>q; // 优先队列模拟堆 for (int i = 1; i <= ni; i ++ ){ q.push({a[i],i}); } int fish=0; while (q.size()&&dt>0) // 只要还有时间就可以钓 { auto t = q.top(); q.pop(); int id = t.y; fish+=t.x; dt--; t.x-=d[id]; // 更新下一分钟能钓的数量 if (t.x>0) q.push({t.x,id}); } res = max(res,fish); }
————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
归并排序（基础）
逆序对：
逆序数的定义：如果 i < j 且A[i] > A[j].则A[i]和A[j]即为逆序数对．逆序数对的个数就叫逆序数．因此求逆序数可以通过管理两个指针，两次扫描数组，蛮力法求出，显然时间复杂度是Θ(n^2).那么有更快的办法吗？答案是肯定的，利用归并排序法，稍做改进即可．在Merge()中，合并两个已经有序的数组A,B.因为A.B有序,所以,A,B各自的逆序数是0,所以AB的逆序数等于A,B之间的逆序数.
——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
归并排序：
归并排序是分治法(分而治之)的一种典型应用，应用递归的思想，自顶向下思考：先假定MergeSort()可以将一个乱序的数组排好序，因此就可以开始”分”(将一个数组平均分成两部分），再”治”(分别对前后部分调用MergeSort()使它们有序)，最后再写一个合并子函数Merge()，它可以将两个有序的数组合并，Merge()实现起来比较容易．只需要管理两个指针，分别指向两个子数组的开头，开辟新内存保存中间结果，遍历完两个数组就可以完成，时间是Θ(n).
假定n个元素的数组调用MergeSort()需要时间T(n).因此，T(n)=2T(n/2)+Θ(n)．由主定理可知：T(n)=Θ(nlogn).归并排序算法的时间复杂度是Θ(nlogn)，空间复杂度是Θ(n).
题目：
https://www.acwing.com/activity/content/code/content/8005520/
模板：
ll merge_sort(int l,int r){ if(l>=r) return 0; int mid = (l+r)/2; ll res= merge_sort(l,mid)+merge_sort(mid+1,r); int k=0;int i=l;int j=mid+1; while(i<=mid&&j<=r){ if(a[j]>=a[i]) t[k++]=a[i++]; else{t[k++]=a[j++];res=res+mid - i + 1;} } while(i<=mid) t[k++]=a[i++]; while(j<=r) t[k++]=a[j++]; for(i=l,j=0;j <k;j++,i++){ a[i]=t[j]; } return res; }