快速排序

//模板一
void quick_sort(int q[], int L, int R){
    if(L >= R) return ;
    int i = L, j = R, x = q[L + R >> 1];
    while(i < j){
        while(q[i] < x) i++;
        while(q[j] > x) j--;
        if(i <= j){
            swap(q[i], q[j]), i++, j--;
        }
    }
    quick_sort(q, L, j), quick_sort(q, i, R);
}
//模板二
void quick_sort(int q[], int L, int R){
    if(L >= R) return ;
    int 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);
}

归并排序

void merge_sort(int q[], int L, int R){
    if(L >= R) return ;
    int mid = L + R >> 1;
    merge_sort(q, L, mid), merge_sort(q, mid + 1, R);
    int k = 0, i = L, j = mid + 1;
    while(i <= mid && j <= R)
        q[i] <= q[j] ? tmp[k++] = q[i++] : tmp[k++] = q[j++]; //q[i] < q[j]选第一个是为了保证稳定
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= R) tmp[k++] = q[j++];
    for(int i = L, j = 0; i <= R; i++, j++) q[i] = tmp[j];
}

1. 归并排序与快速排序中的第一步的选取区别为，归并排序选取的中间下标值，而快速排序可以选取数组中的任意值。
2. 归并排序与快速排序都是基于分治思想
3. 快速排序交换次数少，归并需要开辟两个数组
4. 归并排序如果序列中有两个及以上是相同的那么选取第一个因为归并排序是稳定的
5. 快排也可以变为稳定排序，把下标也放进来。

二分

整数二分

//模板一
bool check(int x){} //检查x是否符合规则
int bsearch_1(int L, int R){ //右面的都符合规则
    while(L < R){
        int mid = L + R >> 1;
        if(check(mid)) R = mid;
        else L = mid + 1;
    }
    return L;
}
//模板二
int bsearch_2(int L, int R){ //左面的都符合规则
    while(L < R){
        int mid = L + R + 1 >> 1;
        if(check(mid)) L = mid;
        else R = mid - 1;
    }
    return L;
}

浮点数二分

bool check(double x){} //检查x是否符合规则
double bsearch_3(double L, double R){
    const double eps = 1.0e-6; //eps表示精度,根据经验值保留k位小数则为1.0e-(k+2)
    while(R - L > eps){
        double mid = (L + R) / 2;
        if(check(mid)) r = mid;
        else L = mid;
    }
    return L;
}

整数二分和浮点数二分的区别是浮点数二分不用考虑边界
两个整数二分模板视分析而定
二分不是只有单调才可以用，只要符合规则就可以。

高精度

高精度加法

//模板一
string big_add(string s1, string s2){
    if(s1.size() < s2.size()) return big_add(s2, s1);
    s2.insert(0, s1.length() - s2.length(), '0');
    string s = s1;
    int cnt = 0;
    for(int i = s1.size() - 1; i >= 0; i--){
        cnt = s1[i] + s2[i] + cnt - 96;
        s[i] = cnt % 10 + 48;
        cnt /= 10;
    }
    if(cnt > 0) s = "1" + s;
    return s;
}
//模板二
vector<int> big_add(vector<int> &A, vector<int> &B){
    if(A.size() < B.size()) return big_add(B, A); //这句直接返回是一个好的方法不用引入第三变量。
    vector<int> C;
    int t = 0;
    for(int i = 0; i < A.size(); i++){
        t += A[i];
        if(i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    if(t) C.push_back(t);
    return C;
}

int main(){
    string s1, s2;
    cin >> s1 >> s2;
    vector<int> A, B;
    for(int i = s1.size() - 1; i >= 0; i--) A.push_back(s1[i] - 48);
    for(int i = s2.size() - 1; i >= 0; i--) B.push_back(s2[i] - 48);
    auto C = big_add(A, B);
    for(int i = C.size() - 1; i >= 0; i--) cout << C[i];
    return 0;
}

高精度减法

//模板一
string big_sub(string s1, string s2){
    if(s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2)) return big_sub(s2, s1);
    s2.insert(0, s1.length() - s2.length(), '0');
    string s = s1;
    for(int i = s1.size() - 1, cnt = 0; i >= 0; i-- ){
        cnt = s1[i] - s2[i] - cnt;
        s[i] = (cnt + 10) % 10 + 48;
        cnt < 0 ? cnt = 1 : cnt = 0;
    }
    int k = 0;
    while(s[k] == '0' && k < s.size() - 1) k++; s.erase(0, k);
    return s;
}
//模板二
bool cmp(vector<int>& A, vector<int> &B)
{
    if(A.size() != B.size()) return A.size() > B.size(); 
    for(int i = A.size() - 1; i >= 0; i--)
        if(A[i] != B[i]) return A[i] > B[i];
    return true;
}

vector<int> big_sub(vector<int> &A, vector<int> &B){
    if(!cmp(A, B)) return big_sub(B, A);
    for (int i = 0, t = 0; i < A.size(); i++){
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back(); //去除前导0
    return C;
}

高精度与低精度乘法

低精度指的是可以用基本数据类型储存

//模板一
string big_mul(string s1, string s2){
    if(s2 == "0") return "0";
    string s;
    for(int i = s1.size() - 1, t = 0; i >= 0 || t; i--){
        if(i < s1.size()) t += (s1[i] - 48) * stoi(s2);
        s = (char)(t % 10 + 48) + s;
        t /= 10;
    }
    return s;
}
//模板二
vector<int> big_mul(vector<int> &A, int b){
    vector<int> C;
    for(int i = 0, t = 0; i < A.size() || t; i++){
        if(i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while(C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度与低精度除法

模板一
string big_div(string s1, string s2, int &r){
    string s;
    for(int i = 0; i < s1.size(); i++){
        r =  r * 10 + s1[i] - 48;
        s = s + (char)(r / stoi(s2) + 48);
        r %= stoi(s2);
    }
    int k = 0;
    while(s[k] == '0' && k < s.size() - 1) k++; s.erase(0, k);
    return s;
}
模板二
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

在高精度加减法中用模板一更快，乘除法中用模板二更快，对于模板二main中的输入输出格式是相同的。

前缀和

一维前缀和

s[i] = a[1] + a[2] + ... + a[i]
a[L] + ... + a[R] = S[R] - S[L - 1]

二维前缀和

s[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

差分

一维差分

给区间[L, R]中的每一个数加上c：b[L] += c, b[R + 1] -= c;

二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c;

双指针算法

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

位运算

求n的第k位数字n >> k & 1
例子：10的二进制1010

#include <iostream>

using namespace std;

int main() {
    unsigned a = 10;
    for(int i = 3; i >= 0; i --) cout << (a >> i & 1);
    return 0;
}

返回n的最后一位1lowbit(n) = n & -n

// lowbit 实现
int lowbit(int x)  { // 返回末尾的1
    return x & -x;
    // return x & (~x + 1);
}

离散化

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

区间合并

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

---

数据结构

链表(数组模拟，静态链表，速度快)

单链表

1. 单链表在算法中多用邻接表
2. 邻接表在用在图和树的储存

#include <iostream>

using namespace std;

const int maxn = 100010;
//head为头结点的地址，idx为当前结点的地址，ne[]为next的结点的指针，e为当前结点的值
int head, idx, e[maxn], ne[maxn];
//初始化
void init(){
    head = -1;
    idx = 0;
}
//在头结点插入一个数n
void insert2head(int n){
    e[idx] = n, ne[idx] = head, head = idx++;
}
//在一个结点后新新插入一个数
void insert2x(int k, int x){
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}
//将头结点删除（需要保证头结点的存在需要特判）在调用之前特判if(!k) head = ne[head]
void removek(int k){
    ne[k] = ne[ne[k]];
}
int main{
    return 0;
}

邻接表

一些单链表的集合

双链表

1. 优化某些问题

// e[]表示节点的值，L[]表示节点的左指针，R[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], L[N], R[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    R[0] = 1, L[1] = 0;
    idx = 2;
}

// 在节点k的右边插入一个数x
void insert2x(int k, int x)
{
    e[idx] = x;
    L[idx] = k, R[idx] = R[k];
    L[R[k]] = idx, R[k] = idx ++ ;
}

// 删除节点a
void removek(int x)
{
    L[R[x]] = L[x];
    R[L[x]] = R[x];
}

---

栈与队列:单调队列、单调栈

栈

先进后出

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
if (tt > 0){

}

单调栈

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ ){
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

队列

普通队列

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh <= tt){

}

循环队列

// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt){

}

单调队列

常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

---

kmp

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

Trie树

快速存储字符串的集合的数据结构

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str){
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str){
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

并查集

Union(并) / Find(查) / Set(集)

将两个集合合并
询问两个元素是否在一个集合当中
基本原理：每个集合用一棵树来表示.树根的编号就是整个集合的编号。每个结点储存它的父结点，p[x]表示x的父结点。
如何判断树根：if(p[x] == x)
如何求x的集合编号：while(p[x] != x) x = p[x];
如何合并两个集合：p[x]是x的集合编号，p[y]u是y的集合编号，p[x] = y;
优化：路径压缩

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x){
        return q[x] == x ? x : q[x] = find(q[x]);
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：给祖宗结点认一个爹
    p[find(a)] = find(b);

(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

堆

维护一个数据集合

1. 插入一个数
2. 求集合当中的最小值
3. 删除最小值
4. 删除任意一个元素
5. 修改任意一个元素

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

哈希

一般哈希

根据处理冲突分为拉链法和开放寻址法
离散化是一种特殊的哈希思想

(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x){
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x){
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

(2) 开放寻址法(常用)
> 数组开放2~3倍
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

字符串哈希

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

C++STL简介

vector, 变长数组，倍增的思想(减少申请次数)
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

---