持续更新~

非特殊说明应该都属于algorithm头文件

二路归并 $inplace\_merge\ O(n)$

同一数组的归并。
inplace_merge(begin, middle, end)

指针 begin~middle- 1 和 middle~end- 1 的归并。

用该函数写成的归并排序样例程序如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int arr[N];

void merge_sort(int l,int r) {
    if(l==r) return;
    int mid=(l+r)>>1;
    merge_sort(l,mid), merge_sort(mid+1,r);
    inplace_merge(arr+l, arr+mid+1, arr+r+1);
}

int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    merge_sort(1,n);
    for(int i=1;i<=n;i++) cout<<arr[i]<<' ';
    return 0;
}

二分查找 $lower\_bound\ O(n \log n)$

主要讲讲自定义函数的用法。

四个参数：lower_bound(begin, end, val, <compare>)，第四个是自定义比较函数，等价于重载<运算符。

bool cmp(const int &a, const int &b) { return a<b; }

cmp 一般这么写。
需要提醒的一点是，a 是数组里的元素，而 b 是被比较的元素。

快速查找 $nth\_element\ O(n)$

引用 https://blog.csdn.net/dylan_frank/article/details/77893811

找到数组中的第 k 大元素，将其放在 k 位置，左边的元素皆比其小，右边的元素皆比其大，且右边一定有序。
nth_element(first, nth, last)

first，last 第一个和最后一个迭代器，也可以直接用数组的位置。
nth，要定位的第 n 个元素，能对它进行随机访问.

nth 同属于迭代器。
常用于 K -DTree 或中位数查找。

字符串库函数 (C++11)

类型 wstring 宽字符串，可包含非 ASCII 字符，如 Unicode 等

stoi stol stoll 字符串转化为有符号整数
stoul stoull 字符串转化为无符号整数
stof stod stold 字符串转化为浮点数
to_string 整数 / 浮点数化为 string

pop_back 移除末尾字符