myTemplateBackup

ICPC 常用算法模板

flowchart LR
ICPC---3["Search"]
ICPC---4["Data Structure"]
ICPC---5["Dynamic Programming"]
ICPC---6["Number Theory、Linear Algebra"]
ICPC---7["Combinatorics、Polynomial"]
ICPC---8["Geometry"]
ICPC---9["String"]
ICPC---10["Graph Theory"]

目录

[TOC]

基本算法

尺取法/双指针

$O(n)$

// 尺取法获取第k近的点下标
void getKth(int k) {
    int l = 1, r = k + 1;
    nxt[1] = k + 1;
    for (int i = 2; i <= n; i++) {
        while (r + 1 <= n && a[i] - a[l] > a[r + 1] - a[i])
            l++, r++;
        if (a[i] - a[l] < a[r] - a[i])
            nxt[i] = r;
        else
            nxt[i] = l;
    }
}

void add(int x) { if (++mp[a[x]] == 1) cnt++; }
void del(int x) { if (--mp[a[x]] == 0) cnt--; }
// 尺取法，f[i] 表示区间 [i, f[i]] 中有k个不同的数
for (int l = 1, r = 1; l <= n; l++) {
    while (cnt < k && r <= n)
        add(r++);
    if (cnt == k)
        f[l] = r - 1;
    else
        f[l] = n + 1;
    del(l);
}

void add(int x) { sum += a[x]; }
void del(int x) { sum -= a[x]; }
sum = 0, res = n + 1;
// 查询满足区间和大于等于 s 的最短区间
for (int l = 1, r = 1; l <= n; l++) {
    while (sum < s && r <= n)
        add(r++);
    if (sum < s)
        break;
    res = min(res, r - l);
    del(l);
}

二分和二分答案

$O(\log n)$

int l, r， m; // [l,r)
while (r - l > 1)
	if (check(m = (l + r) / 2))
		l = m;
	else
		r = m;
// l : last true
// r : first false
// lower_bound(x) | check(mid) <x -> r |
// upper_bound(x) | check(mid)<=x -> r |

倍增

快速幂式

$O(n\log m)$

// n个点跳跃m次位置
vector<ll> f(nxt);
for (; m; m >>= 1) {
    if (m & 1)
        for (int i = 1; i <= n; i++)
            ans[i] = f[ans[i]]; //从上次的位置接着跳
    vector<ll> ff(f);
    for (int i = 1; i <= n; i++)
        f[i] = ff[ff[i]]; //倍增跳
}

朴素式

$O(n\log m)$

// 初始化
vector<vector<ll>> f(n + 1, vector<ll>(__lg(m) + 2));
for (int i = 1; i <= n; i++)
    f[i][0] = nxt[i];
for (int t = 1; t <= __lg(m) + 1; t++)
    for (int i = 1; i <= n; i++)
        f[i][t] = f[f[i][t - 1]][t - 1];
// 查询
int p = 1;
for (int t = __lg(m) + 1; t >= 0; t--)
	if (f[p][t] is 合法) {
        p = f[p][t];
        其他操作
    }

前缀和与差分

一维

前缀和: $p{r}_i=p{r}_{i-1}+a_i$

差分: $d{f}_i=a_i-a_{i-1}$

差分区间修改:

$$\mathrm{add}(l,r,k)\to \{\begin{array}{l}d{f}_l\leftarrow d{f}_l+k\\ d{f}_{r+1}\leftarrow d{f}_{r+1}-k\end{array}$$

二维

前缀和: $p{r}_{i,j}=p{r}_{i,j-1}+p{r}_{i-1,j}-p{r}_{i-1,j-1}+a_{i,j}$

差分: $d{f}_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1}$

差分区间修改:

$$\mathrm{add}((x_1,y_1),(x_2,y_2),k)\to \{\begin{array}{l}d{f}_{x_1,y_1}\leftarrow d{f}_{x_1,y_1}+k\\ d{f}_{x_1,y_2+1}\leftarrow d{f}_{x_1,y_2+1}-k\\ d{f}_{x_2+1,y1}\leftarrow d{f}_{x_2+1,y1}-k\\ d{f}_{x_2+1,y_2+1}\leftarrow d{f}_{x_2+1,y_2+1}+k\end{array}$$

高维

前缀和:

• 容斥原理:

$$\underset{s\in U}{\mathrm{for}}p{r}_s=\sum _{r=\underset{n}{\underbrace{00\cdots 01}}}^{\stackrel{n}{\overbrace{11\cdots 11}}}(-1{)}^{\mathrm{popcount}(r)+1}p{r}_{s-r}+a_s，s-r\text{表示按位减}$$

• SOS DP:

$$\underset{i=1}{\overset{n}{\mathrm{for}}}\underset{s\in U}{\mathrm{for}}p{r}_s\leftarrow p{r}_s+p{r}_r，r\leftarrow s,r_i\leftarrow r_i-1$$

• 对于每一维度空间都是2的情况，有

$$\underset{i=1}{\overset{n}{\mathrm{for}}}\underset{s\in U}{\mathrm{for}}p{r}_s\leftarrow p{r}_s+p{r}_{s\oplus (1<<i)}\mathrm{if}{s}_i=1$$

差分:

$$\underset{s\in U}{\mathrm{for}}d{f}_s=\sum _{r=\underset{n}{\underbrace{00\cdots 01}}}^{\stackrel{n}{\overbrace{11\cdots 11}}}(-1{)}^{\mathrm{popcount}(r)}{a}_{s-r}+a_s$$

树上

前缀和: 设 $p{r}_i$ 表示结点 $i$ 到根节点的权值总和。

• 若是点权, $x,y$ 路径上的和为 $p{r}_x+p{r}_y-p{r}_{lca}-p{r}_{fa(lca)}$。
• 若是边权, $x,y$ 路径上的和为 $p{r}_x+p{r}_y-2\cdot p{r}_{lca}$。

差分:

对于一次 $\delta (s,t)$ 的访问

• 点差分:

$$\{\begin{array}{l}{d}_s\leftarrow d_s+1\\ d_{lca}\leftarrow d_{\text{lca}}-1\\ d_t\leftarrow d_t+1\\ d_{fa(lca)}\leftarrow d_{fa(lca)}-1\end{array}$$

• 边差分:

$$\{\begin{array}{l}{d}_s\leftarrow d_s+1\\ d_t\leftarrow d_t+1\\ d_{lca}\leftarrow d_{lca}-2\end{array}$$

离散化

$a\{1,10,100,1000\}\to a\{1,2,3,4\},d\{1,10,100,1000\}$

将 $a_i$ 数组离散化，逆映射保存在 $d_i$ 中。$d:a_i^{\prime }\to a_i$

$O(n\log n)$

int compress(vector<pii> &a, vector<int> &d) {
    for (auto &[l, r] : a)
        d.push_back(l), d.push_back(r);
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());
    auto get = [&d](int x) { return lower_bound(d.begin(), d.end(), x) - d.begin(); };
    for (auto &[l, r] : a)
        l = get(l), r = get(r);
    return d.size();
}
// 离散后修改
vector<int> f(compress(a, d));
for (auto &[l, r] : a)
    fill(f.begin() + l, f.begin() + r, 1);
// 逆映射到离散前的原数值
for (int i = 0; i < f.size() - 1; i++)
    if (f[i])
        ans += d[i + 1] - d[i];

二维的可以对两个维度分别离散化

排列和组合枚举

全排列

$O(n!)$

vector<int> a(n);
iota(a.begin(), a.end(), 1);
do {
    // 判断排列的合法性
} while (next_permutation(a.begin(), a.end()));

组合

$O(2^n)$

int n = 4;
vector<int> a(n + 1);
for (int i = 0; i < (1 << n); i++) {
    int cnt = __builtin_popcount(i);
    a[cnt]++;
    for (int j = 0; j < n; j++)
        if (i >> j & 1) {
            // 判断某位
        }
}
for (int i = 0; i <= n; i++)
    cout << a[i] << " ";

数据结构

单调栈

维护某值的左边第一大，右边第一小 $O(n)$

stack<int> s;
for (int i = 0; i < n; i++) {
    while (!s.empty() && a[s.top()] < a[i]) {// 单调递减栈
        // 此时a[i]是第一个 > a[s.top()]的数
        s.pop();
    }
    // 此时a[i]左边有 s.size() 个 >= a[i] 的数
    // 此时a[i]是第一个 <= a[s.top()]的数
    s.push(i);
}

单调队列

维护k区间最值 $O(n)$

deque<int> q;
for (int i = 0; i < n; i++) {
    while (!q.empty() && i - q.front() >= k) // 调整覆盖范围
        q.pop_front();
    while (!q.empty() && a[q.back()] < a[i]) // 保持单调递减
        q.pop_back();
    q.push_back(i);
    if (i >= k - 1)
        cout << a[q.front()] << endl; // 区间[i-k+1,i]最大值
}

ST表/稀疏表/Sparse Table

维护区间最值

预处理: $O(n\log n)$

查询: $O(1)$

template <typename T, T (*op)(T, T)> struct SparseTable {
    int n, logn;
    vector<vector<T>> dat;
    SparseTable(const vector<T> &v) : n(v.size()), logn(__lg(n) + 1), dat(n + 1, vector<T>(logn + 1)) {
        for (int i = 1; i <= n; i++)
            dat[i][0] = v[i - 1];
        for (int j = 1; j <= logn; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                dat[i][j] = op(dat[i][j - 1], dat[i + (1 << j - 1)][j - 1]);
    }
    T query(int l, int r) {
        int s = __lg(r - l + 1);
        return op(dat[l][s], dat[r - (1 << s) + 1][s]);
    }
};
int maxn(int a, int b) { return a > b ? a : b; }

并查集

维护集合的合并与查询是否相交

初始化: $O(n)$

查询/合并: $O(\log n)$

struct DisjointSet {
    vector<int> p;
    DisjointSet(int n = 1e6) : p(n) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
    void merge(int x, int y) { p[find(y)] = find(x); }
};

树状数组

维护具有区间减性质的序列，维护序列的前缀和信息

单点修改: $O(\log n)$

区间查询: $O(\log n)$

 
template <typename T> struct BIT {
    int size;
    vector<T> dat;
    BIT(int n = 0) : size(n), dat(n + 1, 0) {}
    inline int lowbit(int x) { return x & -x; }
    void add(int i, T x) {
        for (; i <= size; i += lowbit(i))
            dat[i] += x;
    }
    T get(int i) {
        T res = 0;
        for (i = min(i, size); i; i -= lowbit(i))
            res += dat[i];
        return res;
    }
    vector<int> value() {
        vector<int> val(size + 1);
        for (int i = 1; i <= size; i++) val[i] = get(i);
        for (int i = size; i >= 1; i--) val[i] -= val[i - 1];
        return val;
    }
    T query(int l, int r) { return get(r) - get(l - 1); }
    int kthLe(int k) {
        int l = 0, r = size + 1, mid;
        while (r - l > 1)
            get(mid = (l + r) >> 1) < k ? l = mid : r = mid;
        return r;
    }
    int kthGe(int k) {
        int l = 0, r = size + 1, mid;
        int sum = get(size);
        while (r - l > 1)
            sum - get(mid = (l + r) >> 1) < k ? r = mid : l = mid;
        return r;
    }
};

线段树

维护“满足幺半群（封闭性；结合律；幺元）的性质的信息”的序列

如区间和、区间积、区间最大/小值、区间异或等可合并信息

zkw线段树

非递归实现，常数小，功能有限。

初始化建树: $O(n)$

单点修改: $O(\log n)$

区间查询: $O(\log n)$

template <typename T, T (*op)(T, T), T (*e)()> class SegmentTree {
    int n;
    vector<T> dat;
 
  public:
    SegmentTree(const int _n) : n(2 << __lg(_n - 1)), dat(n << 1, e()) {}
    SegmentTree(const vector<T> &v) : n(2 << __lg(v.size() - 1)), dat(n << 1, e()) {
        copy(v.begin(), v.end(), dat.begin() + n);
        for (int p = n - 1; p; p--)
            dat[p] = op(dat[p << 1], dat[p << 1 | 1]);
    }
    void update(int i, T k) { // update[i]=k
        for (dat[i += n] = k; i; i >>= 1)
            dat[i >> 1] = op(dat[i], dat[i ^ 1]);
    }
    T query(int i, int j) { // query[i,j]
        T res = e();
        for (i += n, j += n; i <= j; i >>= 1, j >>= 1) {
            res = i & 1 ? op(res, dat[i++]) : res;
            res = j & 1 ? res : op(res, dat[j--]);
        }
        return res;
    }
};
template <typename T> T Add(T a, T b) { return a + b; }
template <typename T> T e() { return 0; }

线段树

结构体实现，可扩展性强；lazy-tag 延迟更新。

维护 operator+ pushup apply pushdown 实现区间信息合并、标记与下传。

初始化建树: $O(n)$

区间修改: $O(\log n)$

区间查询: $O(\log n)$

单点修改

template <typename Info> struct SegmentTree {
    int n;
    vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_) : n(n_), info(4 << __lg(n)) {}
    SegmentTree(const vector<Info> &a) : SegmentTree(a.size()) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r)
                return void(info[p] = a[l - 1]);
            int m = (l + r) / 2;
            build(p << 1, l, m);
            build(p << 1 | 1, m + 1, r);
            info[p] = info[p << 1] + info[p << 1 | 1];
        };
        build(1, 1, n);
    }
    void modify(int p, int l, int r, int i, const Info &v) {
        if (i < l || r < i)
            return;
        if (l == r)
            return void(info[p] = v);
        int m = (l + r) / 2;
        modify(p << 1, l, m, i, v);
        modify(p << 1 | 1, m + 1, r, i, v);
        info[p] = info[p << 1] + info[p << 1 | 1];
    }
    void modify(int x, const Info &v) { modify(1, 1, n, x, v); }
    Info rangeQuery(int p, int l, int r, int a, int b) {
        if (b < l || r < a)
            return Info();
        if (a <= l && r <= b)
            return info[p];
        int m = (l + r) / 2;
        return rangeQuery(p << 1, l, m, a, b) + rangeQuery(p << 1 | 1, m + 1, r, a, b);
    }
    Info rangeQuery(int a, int b) { return rangeQuery(1, 1, n, a, b); }
};

区间修改

template <typename Info, typename Tag> struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_) : n(n_), info(4 << __lg(n)), tag(4 << __lg(n)) {}
    LazySegmentTree(const vector<Info> &a) : LazySegmentTree(a.size()) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r)
                return void(info[p] = a[l - 1]);
            int m = (l + r) / 2;
            build(p << 1, l, m);
            build(p << 1 | 1, m + 1, r);
            info[p] = info[p << 1] + info[p << 1 | 1];
        };
        build(1, 1, n);
    }
    void apply(int p, int l, int r, const Tag &v) {
        info[p].apply(l, r, v);
        tag[p].apply(l, r, v);
    }
    void pushdown(int p, int l, int r) {
        int m = (l + r) / 2;
        apply(p << 1, l, m, tag[p]);
        apply(p << 1 | 1, m + 1, r, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (x < l || r < x)
            return;
        if (l == r)
            return void(info[p] = v);
        pushdown(p, l, r);
        int m = (l + r) / 2;
        modify(p << 1, l, m, x, v);
        modify(p << 1 | 1, m + 1, r, x, v);
        info[p] = info[p << 1] + info[p << 1 | 1];
    }
    void modify(int x, const Info &v) { modify(1, 1, n, x, v); }
    void rangeApply(int p, int l, int r, int a, int b, const Tag &v) {
        if (b < l || r < a)
            return;
        if (a <= l && r <= b)
            return apply(p, l, r, v);
        pushdown(p, l, r);
        int m = (l + r) / 2;
        rangeApply(p << 1, l, m, a, b, v);
        rangeApply(p << 1 | 1, m + 1, r, a, b, v);
        info[p] = info[p << 1] + info[p << 1 | 1];
    }
    void rangeApply(int a, int b, const Tag &v) { rangeApply(1, 1, n, a, b, v); }
    Info rangeQuery(int p, int l, int r, int a, int b) {
        if (b < l || r < a)
            return Info();
        if (a <= l && r <= b)
            return info[p];
        pushdown(p, l, r);
        int m = (l + r) / 2;
        return rangeQuery(p << 1, l, m, a, b) + rangeQuery(p << 1 | 1, m + 1, r, a, b);
    }
    Info rangeQuery(int a, int b) { return rangeQuery(1, 1, n, a, b); }
};
struct Tag {
    int x;
    void apply(int l, int r, const Tag &v) { x += v.x; }
};
struct Info {
    ll sum = 0;
    void apply(int l, int r, const Tag &v) { sum += (r - l + 1) * v.x; }
    friend Info operator+(Info a, Info b) { return Info{a.sum + b.sum}; }
};
// void modifty(int a, int b, T k, int p = 1) {
//     if (a <= tr[p].l && tr[p].r <= b)
//         return mark(k, p);
//     pushdown(p);
//     int mid = (tr[p].l + tr[p].r) >> 1;
//     if (a <= mid) modifty(a, b, k, p << 1); // 左半区间与修改区间相交
//     if (b > mid) modifty(a, b, k, p << 1 | 1); // 右半区间与修改区间相交
//     tr[p] = tr[p << 1] + tr[p << 1 | 1];
// }
// Node query(int a, int b, int p = 1) {
//     if (a <= tr[p].l && tr[p].r <= b)
//         return tr[p];
//     pushdown(p);
//     int mid = (tr[p].l + tr[p].r) >> 1;
//     if (b <= mid) return query(a, b, p << 1); // 只有左半区间与查询区间相交
//     else if (a > mid) return query(a, b, p << 1 | 1); // 只有右半区间与查询区间相交
//     else return query(a, b, p << 1) + query(a, b, p << 1 | 1); // (a <= mid < b) 两端区间都与查询区间相交
// }

可持久化线段树/主席树

class SegmentTree {
    struct Node {
        int l = 0, r = 0, sum = 0;
    };
    vector<Node> tr;
    vector<int> rt;
    int n, cnt;
    int update(int k, int d, int p, int l, int r) {
        int q = tr.size();
        tr.push_back(tr[p]);
        if (l == r) {
            tr[q].sum += d;
            return q;
        }
        int mid = (l + r) / 2;
        if (k <= mid)
            tr[q].l = update(k, d, tr[p].l, l, mid);
        else
            tr[q].r = update(k, d, tr[p].r, mid + 1, r);
        tr[q].sum = tr[tr[q].l].sum + tr[tr[q].r].sum;
        return q;
    }
    int kth(int k, int p, int q, int l, int r) {
        if (l == r)
            return l;
        int mid = (l + r) / 2;
        int x = tr[tr[q].l].sum - tr[tr[p].l].sum;
        if (x >= k)
            return kth(k, tr[p].l, tr[q].l, l, mid);
        else
            return kth(k - x, tr[p].r, tr[q].r, mid + 1, r);
    }
 
  public:
    SegmentTree(int n) : n(n), rt(1), cnt(1), tr(1) {}
    void update(int k, int d) { rt.push_back(update(k, d, rt.back(), 1, n)); }
    int kth(int k, int p, int q) { return kth(k, rt[p - 1], rt[q], 1, n); }
};

分块与莫队算法

分块

template <typename T> class Block {
    int n, t, m;
    vector<int> l, r, id;
    vector<T> &v, sum, tag;
    void add(int p, int a, int b, T k) {
        sum[p] += k * (b - a + 1);
        for (int i = a; i <= b; i++)
            v[i] += k;
    }
    T ask(int p, int a, int b) {
        T res = tag[p] * (b - a + 1);
        for (int i = a; i <= b; i++)
            res += v[i];
        return res;
    }
 
  public:
    Block(vector<T> &v) // 1-index
        : n(v.size() - 1), t(sqrt(n)), m(n / t + (n % t > 0)), l(m + 1), r(m + 1), id(n + 1),
    	  v(v), sum(m + 1), tag(m + 1) {
        for (int i = 1; i <= m; i++) {
            l[i] = (i - 1) * t + 1, r[i] = min(i * t, n);
            for (int j = l[i]; j <= r[i]; j++) {
                sum[i] += v[j];
                id[j] = (j - 1) / t + 1;
            }
        }
    }
    void update(int a, int b, T k) {
        int p = id[a], q = id[b];
        if (p == q) {
            add(p, a, b, k);
        } else {
            for (int i = p + 1; i <= q - 1; i++)
                tag[i] += k;
            add(p, a, r[p], k);
            add(q, l[q], b, k);
        }
    }
    T query(int a, int b) {
        T res = 0;
        int p = id[a], q = id[b];
        if (p == q) {
            res += ask(p, a, b);
        } else {
            for (int i = p + 1; i <= q - 1; i++)
                res += sum[i] + tag[i] * (r[i] - l[i] + 1);
            res += ask(p, a, r[p]);
            res += ask(q, l[q], b);
        }
        return res;
    }
};

二叉搜索树&平衡树

vector平衡树

template <typename T> struct BST {
    vector<T> tr;
    void insert(T x) { tr.insert(lower_bound(tr.begin(), tr.end(), x), x); }
    void erase(T x) { tr.erase(lower_bound(tr.begin(), tr.end(), x)); }
    int rank(T x) { return lower_bound(tr.begin(), tr.end(), x) - tr.begin() + 1; }
    int kth(int x) { return tr.at(x - 1); }
    int pre(int x) { return *prev(lower_bound(tr.begin(), tr.end(), x)); }
    int nxt(int x) { return *upper_bound(tr.begin(), tr.end(), x); }
};

图论

存图

邻接表/邻接矩阵

using Node = pair<int, int>;
vector<int> G[N];
int G[N][N]; //
int n, m;
 
for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    G[u].push_back({v, w});
    G[v].push_back({u, w});
    G[u][v] = G[v][u] = w;
}
for (int u = 0; u < n; u++)
    for (auto &[v, w] : G[u]) {}
	for (int v = 0; v < n; v++) if (G[u][v]) {}

链式前向星

struct ChainForwardStar {
    using Edge = pair<int, int>;
    vector<int> head, next;
    vector<Edge> edges;
    int E;
    ChainForwardStar(int V = 0) { head.resize(V + 1, -1); }
    void addEdge(int u, int v, int w = 1) {
        edges.push_back({v, w});
        next.push_back(head[u]);
        head[u] = E++;
    }
};
ChainForwardStar G(n);
for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    G.addEdge(u, v, w);
}
for (int u = 0; u < n; u++)
    for (int i = G.head[u]; ~i; i = G.next[i]) {
        auto &[v, w] = G.edges[i];
        cout << u << " " << v << " " << w << endl;
    }

DFS/BFS

$O(n)$

void dfs(int u) {
    if (vis[u])
        return;
    vis[u] = true;
    for (int v : G[u])
        dfs(v);
}
void bfs(int u) {
    queue<int> Q;
    vis[u] = true;
    Q.push(u);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int v : G[u])
            if (!vis[v]) {
                vis[v] = true;
                Q.push(v);
            }
    }
}

拓扑排序

$O(n)$

vector<int> ans;
queue<int> q;
int indeg[N];
 
bool tsort() {
    queue<int> q;
    vector<int> ans;
    for (int u = 1; u <= n; u++)
        for (int v : G[u])
            indeg[v]++;
    for (int u = 1; u <= n; u++)
        if (indeg[u] == 0)
            q.push(u);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans.push_back(u);
        for (int v : G[u])
            if (--indeg[v] == 0)
                q.push(v);
    }
    return ans.size() == n;
}

最短路径

Dijkstra

朴素算法: $O(n^2)$

堆优化: $O(m\log n)$

int dist[N];
bool vis[N];
 
void dijkstra(int s) {
    memset(0, 0x3f, sizeof(dist));
    dist[s] = 0;
    while (true) {
        int u = -1;
        for (int i = 0; i < V; i++)
            if ((u == -1 || dist[u] > dist[i]) && !vis[i])
                u = i;
        if (u == -1)
            break;
        vis[u] = true;
        for (auto &[v, w] : G[u])
            dist[v] = min(dist[v], dist[u] + w);
    }
}
void dijkstra_heap(int s) {
    priority_queue<Node, vector<Node>, greater<Node>> q;
    memset(0, 0x3f, sizeof(dist));
    dist[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        auto [dist_u, u] = q.top();
        q.pop();
        if (dist[u] < dist_u)
            continue;
        for (auto &[v, w] : G[u])
            if (dist[v] > dist[u] + w)
                q.push({dist[v] = dist[u] + w, v});
    }
}

最小生成树

kurskal

$O(m\log m)$

vector<int> p;
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
 
int kruskal() {
    int sum = 0, cnt = 0;
    p.resize(V + 1);
    iota(p.begin(), p.end(), 0);
    sort(edges.begin(), edges.end());
    for (auto &[u, v, w] : edges)
        if (find(u) != find(v)) {
            sum += w;
            cnt++;
            p[find(u)] = find(v);
        }
    return cnt == V - 1 ? sum : -1;
}

LCA

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n;
vector<int> G[N];
int dep[N], p[N][20];
void dfs(int u, int fa) {
    p[u][0] = fa;
    for (int t = 1; (1 << t) <= dep[u]; t++)
        p[u][t] = p[p[u][t - 1]][t - 1];
    for (int v : G[u])
        if (v != fa) {
            dfs(v, u);
            dep[v] = dep[u] + 1;
        }
}
int LCA(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (dep[x] - (1 << i) >= dep[y])
            x = p[x][i];
    if (x == y)
        return x;
    for (int i = 19; i >= 0; i--)
        if (p[x][i] != p[y][i])
            x = p[x][i], y = p[x][i];
    return p[x][0];
}
int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
}

数学

卷积

for (int k = al + bl - 2; k >= 0; k--) {
    value_type tmp = 0;
    for (int i = std::min(k, (int)al - 1); i >= 0 && k - i < bl; i--)
        tmp += a[i] * b[k - i];
    a[k] = tmp;
}

位运算

快速幂

$O(\log n)$

ll pow(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x)
        if (n & 1)
            s = s * x;
    return s;
}

素数

分解质因数/唯一分解定理

$O(\sqrt{n})$

vector<int> getPrimeFactor(int n) {
    vector<int> res;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0)
                n /= i, cnt++;
            res.push_back(i);
        }
    if (n != 1)
        res.push_back(n);
    return res;
}

素数测试

$O(\sqrt{n})$

bool Prime(int x) {
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
    return x > 1;
}

埃氏筛

$O(n\log \log n)$

vector<int> isPrime, primes;
void eratosthenes(int n) {
    isPrime.assign(n + 1, 1);
    primes.clear();
    isPrime[0] = isPrime[1] = 0;
    for (int i = 2; i <= n; i++)
        if (isPrime[i]) {
            primes.push_back(i);
            for (int j = 2 * i; j <= n; j += i)
                isPrime[j] = 0;
        }
}

线性筛

$O(n)$

vector<int> minp, primes;
void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    for (int i = 2; i <= n; i++) {
        if (!minp[i])
            minp[i] = i, primes.push_back(i);
        for (int j = 0; i * primes[j] <= n; j++) {
            minp[i * primes[j]] = primes[j];
            if (i % primes[j] == 0)
                break;
        }
    }
}

欧几里得（Euclid）算法/辗转相除法

$O(\log n)$

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
// c++14 : __gcd(a, b)
// c++17 : std::gcd(a, b) <numeric>

扩展欧几里得算法

$O(\log n)$

int extgcd(int a, int b, int &x, int &y) {
    int d;
    if (b == 0)
        x = 1, y = 0, d = a;
    else {
        d = extgcd(b, a % b, y, x); // x'  y'
        y -= a / b * x;             // y = y - a / b * x = x' - a / b * y' = y'' - a / b * y'
    }
    return d;
}

数论分块

${\sum }_{i=1}^n{\sum }_{d|i}f(d)={\sum }_{i=1}^{n}f(i)\lfloor \frac{n}{i}\rfloor$

快速计算 ${\sum }_{i=1}^{n}f(i)g(\lfloor \frac{n}{i}\rfloor )$ , 其中 $f(i)$ 可以预处理前缀和 $s(i)$

$O(\sqrt{n})$

int f[N], g[N];
ll s[N];
ll H(int n) {
    ll res = 0;
    for (ll l = 1, r; l <= n; l = r + 1) {
        ll d = n / l;
        r = n / d;
        // res += (r - l + 1) * d;
        res += (s[r] - s[l - 1]) * g[d];
    }
    return res;
}

积性函数

如果有 $\gcd (a,b)=1$ , 那么 $\phi (a\times b)=\phi (a)\times \phi (b)$

欧拉函数

欧拉函数，即 $\phi (n)$，表示的是小于等于 $n$ 和 $n$ 互质的数的个数

当 $n$ 是质数的时候，显然有 $\phi (n)=n-1$

$\phi (n)={\sum }_{i=1}^n[\gcd (i,n)=1]=n\times {\prod }_{i=1}^k$

性质

• 欧拉函数是积性函数
• $n={\sum }_{d\mid n}\phi (d)$
• 若 $n=p^k$ , 其中 $p$ 是质数，那么 $\phi (n)=p^k-p^{k-1}$ （根据定义可知）
• 由唯一分解定理，设 $n={\prod }_{i=1}^s{p}_i^{k_i}$ , 其中 $p_i$ 是质数，有 $\phi (n)=n\times {\prod }_{i=1}^s\frac{p_i-1}{p_i}$

求一个数欧拉函数的值

$O(\sqrt{n})$

int euler_phi(int n) 
  int ans = n;
  for (int i = 2; i * i<= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}

求多个数的欧拉函数值

$O(n)$

void init_phi(int n) {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[1] = false;
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt && ll(i) * prime[j] <= n; j++) {
            isPrime[i * prime[j]] = false;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else {
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            }
        }
    }
}

欧拉定理

若 $\gcd (a,m)=1，则a^{\phi (m)}\equiv 1(\mathrm{mod}m)$

费马小定理

若 $p$ 为素数，$\gcd (a,p)=1$ ，则 $a^{p-1}\equiv 1(\mathrm{mod}p)$

另一个形式：对于任意整数 $a$，有 $a^p\equiv a(\mathrm{mod}p)$

乘法逆元

如果一个线性同余方程 $ax\equiv 1(\mathrm{mod}b)$ ，则 $x$ 称为 $a\mathrm{mod}b$ 的逆元，记作 $a^{-1}$

扩展欧几里得法

$ax\equiv 1(\mathrm{mod}b)⟺ax+by=1$

int inv(int a, int b) {
    int x, y;
    extgcd(a, b, x, y);
    return x;
}

快速幂法

$ax\equiv 1(\mathrm{mod}b)⟺ax\equiv a^{b-1}(\mathrm{mod}b)⟺x\equiv a^{b-2}(\mathrm{mod}b)$

int inv(int a, int b) { return pow_mod(a, b - 2, b); }

线性同余方程

线性同余方程 $ax\equiv b(\mathrm{mod}n)⟺ax+ny=b$

二元丢番图方程

$ax+by=c⟺(x_0,y_0)$

$$\begin{gathered} x=x_0+(b/d)n \\ y=y_0-(a/d)n \end{gathered}$$

// ax + by = c
bool liEu(int a, int b, int c, int &x, int &y) {
    int d = extgcd(a, b, x, y);
    if (c % d != 0)
        return false;
    x = 1LL * x * c / d;
    y = 1LL * y * c / d;
    return true;
}

x的最小和最大值

void minmax(ll a, ll b, ll c, ll n) {
    ll x0, y0, gcd = extgcd(a, b, x0, y0);
    if (c < 0) {
        cout << -1 << '\n';
        return;
    } else if (c == 0 && gcd == 0) {
        cout << 0 << ' ' << n << '\n';
        return;
    } else if (c == 0) {
        cout << 0 << ' ' << 0 << '\n';
        return;
    } else if (gcd == 0 || c % gcd != 0) {
        cout << -1 << '\n';
        return;
    }
    // c > 0, gcd != 0, c % gcd == 0
    x0 *= c / gcd;
    y0 *= c / gcd;
    ll k_min = ceil(double(-x0) / (b / gcd));
    ll k_max = floor(double(y0) / (a / gcd));
    if (k_min > k_max) {
        cout << -1 << '\n';
        return;
    }
    ll x_min = 1e8, x_max = -1;
    for (ll k = k_min; k <= k_max; k++) {
        ll x_k = x0 + k * (b / gcd);
        ll y_k = y0 - k * (a / gcd);
        if (x_k + y_k <= n) {
            x_min = min(x_min, x_k);
            x_max = max(x_max, x_k);
        }
    }
    cout << x_min << ' ' << x_max << '\n';
}

中国剩余定理

LL CRT(int k, LL* a, LL* r) {
  LL n = 1, ans = 0;
  for (int i = 1; i <= k; i++) n = n * r[i];
  for (int i = 1; i <= k; i++) {
    LL m = n / r[i], b, y;
    exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
    ans = (ans + a[i] * m * b % n) % n;
  }
  return (ans % n + n) % n;
}

模意义下的运算

template <typename T> T pow(T a, long long b) {
    T s = 1;
    for (; b; a = a * a, b >>= 1)
        if (b & 1)
            s = s * a;
    return s;
}
struct Z {
    long long x;
    Z() {}
    Z(long long x) : x(Norm(x)) {}
    static long Norm(long long x) { return x %= mod, x < 0 ? x + mod : x; }
    Z inv() const { return pow(*this, mod - 2); }
    friend Z operator+(const Z &a, const Z &b) { return Z(a.x + b.x); }
    friend Z operator-(const Z &a, const Z &b) { return Z(a.x - b.x); }
    friend Z operator*(const Z &a, const Z &b) { return Z(a.x * b.x); }
    friend Z operator/(const Z &a, const Z &b) { return a * b.inv(); }
    friend ostream &operator<<(ostream &os, const Z &z) { return os << z.x; }
    friend istream &operator>>(istream &is, Z &z) { return os >> z.x, z.x = Norm(z.x), is; }
};

组合数学

排列数和组合数

struct Binom {
    vector<Z> fac, ifac;
    Binom(int n) : fac(n + 1), ifac(n + 1) {
        fac[0] = ifac[0] = 1;
        for (int i = 1; i <= n; i++)
            fac[i] = fac[i - 1] * i;
        ifac[n] = 1 / fac[n];
        for (int i = n - 1; i >= 1; i--)
            ifac[i] = (i + 1) * ifac[i + 1];
    }
    Z C(int m, int n) { return (m < n || n < 0) ? 0 : fac[m] * ifac[n] * ifac[m - n]; }
    Z P(int m, int n) { return (m < n || n < 0) ? 0 : fac[m] * ifac[m - n]; }
} math(N);

线性代数

高斯消元

$O(n^3)$

返回 0 无解，返回 1 有解，解为 $x_i=a[i][n]$

// a:增广矩阵 n*(n+1)
int gauss(vector<vector<double>> &a, int n) {
    for (int i = 0; i < n; i++) { // 枚举列
        int r = i;                // 该列最大数所在的行
        for (int j = i + 1; j < n; j++)
            if (abs(a[j][i]) > abs(a[r][i]))
                r = j;
        if (abs(a[r][i]) < eps)
            return 0;     // 列最大数为0，无解
        swap(a[i], a[r]); // 把这一行移上来
        for (int j = n; j >= i; j--) a[i][j] /= a[i][i];     // 这一行的主元系数变为1
        for (int j = 0; j < n; j++) // 消去主元所在列的其他行的主元
            if (j != i && abs(a[j][i]) > eps)
                for (int k = n; k >= i; k--)
                    a[j][k] -= a[i][k] * a[j][i] / a[i][i];
    }
    return 1;
}
if (!gauss(a, n)) {
    cout << "No Solution" << '\n';
} else {
    for (int i = 0; i < n; i++)
        printf("%.2lf\n", a[i][n]);
}

多项式

FFT

using Poly = vector<int>;
using Complex = complex<double>;
const double eps = 0.49;
const double PI = acos(-1);
int rev[1 << 22];
void FFT(Complex a[], int n, int inv) {
    for (int i = 0; i < n; ++i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << __lg(n >> 1));
    for (int i = 0; i < n; ++i)
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int i = 2; i <= n; i <<= 1) {
        Complex wn(cos(2 * PI / i), inv * sin(2 * PI / i));
        for (int j = 0; j < n; j += i) {
            Complex w0(1, 0);
            for (int k = j; k < j + i / 2; ++k, w0 *= wn) {
                Complex x = a[k], y = w0 * a[k + i / 2];
                a[k] = x + y;
                a[k + i / 2] = x - y;
            }
        }
    }
    if (inv == -1)
        for (int i = 0; i < n; i++)
            a[i] /= n;
}
Poly operator*(Poly a, Poly b) {
    int n = a.size() + b.size() - 1;
    vector<Complex> c(2 << __lg(n - 1));
    for (int i = 0; i < a.size(); i++)
        c[i].real(a[i]);
    for (int i = 0; i < b.size(); i++)
        c[i].imag(b[i]);
    FFT(c.data(), c.size(), 1);
    for (int i = 0; i < c.size(); i++)
        c[i] = c[i] * c[i];
    FFT(c.data(), c.size(), -1);
    Poly s(n);
    for (int i = 0; i < n; i++)
        s[i] = (int)(c[i].imag() / 2 + eps);
    return s;
}

字符串

Tire/字典树

struct Tire {
    int nxt[100000][26], cnt;
    bool exist[100000]; // 该结点结尾的字符串是否存在
 
    void insert(string s) { // 插入字符串
        int p = 0;
        for (char c : s) {
            c -= 'a';
            if (!nxt[p][c])
                nxt[p][c] = ++cnt; // 如果没有，就添加结点
            p = nxt[p][c];
        }
        exist[p] = 1;
    }
 
    bool find(string s) { // 查找字符串
        int p = 0;
        for (char c : s) {
            c -= 'a';
            if (!nxt[p][c])
                return false;
            p = nxt[p][c];
        }
        return exist[p];
    }
};

# def point_in_polygon2(p: Point, polygon: Polygon):
#     """判断点是否在多边形内部"""
#     num = 0
#     for edge in polygon.edges:
#         u, v = edge.a, edge.b
#         # 方法1:
#         # if u.x < p.x and p.x <= v.x and point_line_relation(p, edge) == -1:
#         #     num ^= 1
#         # if v.x < p.x and p.x <= u.x and point_line_relation(p, edge) == 1:
#         #     num ^= 1
#         # 方法2：
#         c = sgn(cross(p - u, v - u))
#         if u.x < p.x and p.x <= v.x and c > 0:
#             num += 1
#         if v.x < p.x and p.x <= u.x and c < 0:
#             num -= 1
#     return num


// bool segmentInPolygon(Line l, vector<Vector> p) {
//     int n = p.size();
//     if (!pointInPolygon(l.a, p)) {
//         return false;
//     }
//     if (!pointInPolygon(l.b, p)) {
//         return false;
//     }
//     for (int i = 0; i < n; i++) {
//         auto u = p[i];
//         auto v = p[(i + 1) % n];
//         auto w = p[(i + 2) % n];
//         auto [t, p1, p2] = segmentIntersection(l, Line(u, v));

//         if (t == 1) {
//             return false;
//         }
//         if (t == 0) {
//             continue;
//         }
//         if (t == 2) {
//             if (pointOnSegment(v, l) && v != l.a && v != l.b) {
//                 if (((v - u) ^ (w - v)) > 0) {
//                     return false;
//                 }
//             }
//         } else {
//             if (p1 != u && p1 != v) {
//                 if (pointOnLineLeft(l.a, Line(v, u)) || pointOnLineLeft(l.b, Line(v, u))) {
//                     return false;
//                 }
//             } else if (p1 == v) {
//                 if (l.a == v) {
//                     if (pointOnLineLeft(u, l)) {
//                         if (pointOnLineLeft(w, l) && pointOnLineLeft(w, Line(u, v))) {
//                             return false;
//                         }
//                     } else {
//                         if (pointOnLineLeft(w, l) || pointOnLineLeft(w, Line(u, v))) {
//                             return false;
//                         }
//                     }
//                 } else if (l.b == v) {
//                     if (pointOnLineLeft(u, Line(l.b, l.a))) {
//                         if (pointOnLineLeft(w, Line(l.b, l.a)) && pointOnLineLeft(w, Line(u,
//                         v)))
//                         {
//                             return false;
//                         }
//                     } else {
//                         if (pointOnLineLeft(w, Line(l.b, l.a)) || pointOnLineLeft(w, Line(u,
//                         v)))
//                         {
//                             return false;
//                         }
//                     }
//                 } else {
//                     if (pointOnLineLeft(u, l)) {
//                         if (pointOnLineLeft(w, Line(l.b, l.a)) || pointOnLineLeft(w, Line(u,
//                         v)))
//                         {
//                             return false;
//                         }
//                     } else {
//                         if (pointOnLineLeft(w, l) || pointOnLineLeft(w, Line(u, v))) {
//                             return false;
//                         }
//                     }
//                 }
//             }
//         }
//     }
//     return true;
// }

// vector<Vector> hp(vector<Line> lines) {
//     sort(lines.begin(), lines.end(), [&](const Line &l1, const Line &l2) {
//         Vector d1 = l1.b - l1.a;
//         Vector d2 = l2.b - l2.a;

//         if (d1.toward() != d2.toward()) {
//             return d1.toward() == 1;
//         }

//         return (d1 ^ d2) > 0;
//     });

//     deque<Line> ls;
//     deque<Vector> ps;
//     for (auto l :lines) {
//         if (ls.empty()) {
//             ls.push_back(l);
//             continue;
//         }

//         while (!ps.empty() && !pointOnLineLeft(ps.back(), l)) {
//             ps.pop_back();
//             ls.pop_back();
//         }

//         while (!ps.empty() && !pointOnLineLeft(ps[0], l)) {
//             ps.pop_front();
//             ls.pop_front();
//         }

//         if (((l.b - l.a) ^ (ls.back().b - ls.back().a)) == 0) {
//             if (((l.b - l.a) * (ls.back().b - ls.back().a)) > 0) {

//                 if (!pointOnLineLeft(ls.back().a, l)) {
//                     assert(ls.size() == 1);
//                     ls[0] = l;
//                 }
//                 continue;
//             }
//             return {};
//         }

//         ps.push_back(lineIntersection(ls.back(), l));
//         ls.push_back(l);
//     }

//     while (!ps.empty() && !pointOnLineLeft(ps.back(), ls[0])) {
//         ps.pop_back();
//         ls.pop_back();
//     }
//     if (ls.size() <= 2) {
//         return {};
//     }
//     ps.push_back(lineIntersection(ls[0], ls.back()));

//     return vector(ps.begin(), ps.end());
// }