参考基本算法-分治法（快排，归并）-CSDN博客 模板进行练习，旨在加强两个模板运用。
1.求逆序对（归并排序）
题目来源：P1908 逆序对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 ai>aj 且 i<j 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。
输入格式：
第一行，一个数 n，表示序列中有 n个数。
第二行 n 个数，表示给定的序列。序列中每个数字不超过 1e9。
输出格式
输出序列中逆序对的数目。
思路
板子题，参考基本算法-分治法（快排，归并）-CSDN博客 归并排序模板加以修改，以cnt作为逆序对的个数。
当q[i]>q[j]时，cnt+=mid-i+1;即可求出逆序对的个数。
注意：此题数据量比较大，要开long long ，用int 过不去。
完整代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
long long q[N],tmp[N],cnt=0;
void merge_sort(long long q[],long long l ,long long r){
if(l>=r) return;
long long mid=l+r>>1;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
long long k=0,i=l,j=mid+1;
while(i<=mid&&j<=r){
if(q[i]<=q[j]) tmp[k++]=q[i++];
else {
tmp[k++]=q[j++];
cnt+=mid-i+1;
}
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(long long i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}
int main(){
long long n;
cin>>n;
for(long long i=0;i<n;i++) scanf("%lld",&q[i]);
merge_sort(q,0,n-1);
cout<<cnt<<endl;
return 0;
}2.求第 k 小的数（快速排序）
题目来源：P1923 【深基9.例4】求第 k 小的数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
输入 n（1≤n<50000001≤n<5000000 且 n 为奇数）个数字 ai（1≤ai<1e9），输出这些数字的第 k 小的数。最小的数是第 0 小。
请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。
思路
方法一：
用快速排序直接排出q[]的大小，输出即可。
完整代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
typedef long long ll;
ll q[N];
void quick_sort(ll q[],ll l,ll r){
if(l>=r) return;
ll i=l-1,j=r+1,x=q[l+r>>1];
while(i<j){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j) swap(q[i],q[j]);
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
int main(){
ll n,m;
cin>>n>>m;
for(int i=0;i<n;i++) scanf("%lld",&q[i]);
quick_sort(q,0,n-1);
cout<<q[m]<<endl;
return 0;
}方法二：
用c++自带STL库函数sort()排除大小，输出即可。
完整代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
typedef long long ll;
ll q[N];
int main(){
ll n,m;
cin>>n>>m;
for(int i=0;i<n;i++) scanf("%lld",&q[i]);
sort(q,q+n);
cout<<q[m]<<endl;
return 0;
}感谢大家的观看！
