分治

快速排序

每次找一个基准值，比基准值小的放左边，比基准值大的放右边，在分别对左右排序
标准代码：

void work(int l,int r)
{
	if (l >= r) return;
	int mid = (l+r)/2;
	mid = a[mid];
	int x = l,y = r;
	while (x <= y)
	{
		while (a[x] < mid) x++;
		while (a[y] > mid) y--;
		if (x <= y) swap(a[x++],a[y--]);
	}
	work(l,y);
	work(x,r);
}

求第k小

只需要枚举第k小所在的区间即可将复杂度将为O（n）

三分

广泛用于单峰函数求最值，因为三个点就可以确定区间

函数

给定n个二次函数，求max(f1(x),f2(x),……,fn(x))在1~1000，中最小值
直接二分x，去出最大值即可
注意掉精度哦

归并排序

先从中间分，把两边排好后再合并

void merge(int l,int r)
{
	int x = l,y = (l+r)/2+1;
	int p = l;
	while (x <= (l+r)/2 && y <= r)
	{
		if (a[x] <= a[y]) b[p++] = a[x++];
		else b[p++] = a[y++];
	}
	while (x <= (l+r)/2) b[p++] = a[x++];
	while (y <= r) b[p++] = a[y++];
	for (int i = l;i <= r;i++) a[i] = b[i];
}
void msort(int l,int r)
{
	if (l >= r) return;
	int mid = (l+r)/2;
	msort(l,mid);
	msort(mid+1,r);
	merge(l,r);
}

逆序对

如果只要后一半与前一半有后面小于前面的答案加加（cnt += m-x+1）

平面最近点对

先算出两边的最小距离d
在以中间的点为中心找出所有距离小于等于d的点
在暴力枚举所有可能