基础知识

排序

快排

核心：先排好一个元素，然后递归排好左边的数组和右边的数组

归并

先排好左边再排好右边，然后merge

归并本质上是一种分而治之的思想

所以这个模板其实可以用于比较广泛的分治的题目，比如求逆序对

这道题就可以采用这个模板，一个数组的逆序对的数量可以分为三个部分，左边数组的逆序对数量，右边数组的逆序对数量和左边和右边的逆序对数量

二分

注意能二分的前提是单调

二分本身并不难，但是容易出错(边界条件），所以建议记牢模板

整数二分

这是如果r=mid的模板

while(l<r)
{
	int mid=l+r>>1;
	if(check(mid))r=mid;
	else l=mid+1;
}

如果是l=mid

while(l<r)
{
	int mid=l+r+1>>1;
	if(check(mid))l=mid;
	else r=mid-1;
}

浮点数二分：

注意浮点数不要直接与0比较，而是应该设置一个很小的数（精度）

注意浮点数不能用移位，然后注意不要定义int习惯了，浮点数一定要小心，但是浮点数二分一般是没有什么边界问题的