基础算法模板

---

数组

数组去重

//n表示有效数组长度
//a[]为预处理的数组，从1开始
//去重后的数组的有效范围为[1,n]
int n,a[maxn];
n=unique(a+1,a+1+n)-a-1;

排序

归并排序

基于分治思想的排序

复杂度稳定为 $O(nlogn)$

递归形式：

//a[]为输入的预排序数组，tmp[]为中间数组
//合并区间为[l,r]
int a[maxn],tmp[maxn];
void Merge(int l,int r){
	int mid=(l+r)>>1,i=l,j=mid+1;
	for(int k=l;k<=r;++k){
		if(i<=mid&&(j>r||a[i]<a[j]))tmp[k]=a[i++];
		else tmp[k]=a[j++];
	}
	for(int i=l;i<=r;++i)a[i]=tmp[i];
}
void MergeSort(int l, int r) {
  	if (r - l<=0) return;//数组长为1不用分解
  	// 分解
  	int mid = (l + r) >> 1;
  	MergeSort(l, mid);
	MergeSort(mid+1, r);
  	// 合并
  	Merge(l,r);
}