Algorithm Template

by Thirstarfish

2026-03-20

杂

头文件

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vec vector
#define endl '\n'
#define fir first
#define sec second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define ppc __builtin_popcount
#define ctz __builtin_ctzll // 去掉define int long long记得修改这里喵
#define clz __builtin_clzll // 还有这里喵
#define pcs(n) cout << fixed << setprecision(n)
#define rvs std::views::reverse
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef tuple<int, int, int, int> t4i;
typedef tuple<int, int, int, int, int> t5i;
typedef tuple<int, int, int, int, int, int> t6i;
typedef array<int, 2> aii;
typedef array<int, 3> aiii;
typedef array<int, 4> a4i;
typedef array<int, 5> a5i;
typedef array<int, 6> a6i;
typedef unsigned long long ull;
typedef long double lld;
typedef __int128_t lll;
const int mod = 998244353; // 1000000000039ll
const int N = 1000005;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const vec<aii> dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const double eps = 1e-6;



void cold_beans()
{

}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    cin >> _; // 单测记得注释这里喵
    while (_--)
        cold_beans();
    return 0;
}

/*
騒がしい日々に笑えない君に
思い付く限り眩しい明日を
*/

cpp

fpow/inv/C/P

ll fpow(ll a, ll b)
{
    ll ans = 1;
    a %= mod; 
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

ll inv(int b) { return fpow(b, mod - 2) % mod; }

vector<ll> jc(N), ijc(N);

void initc(int n)
{
    jc[0] = 1;
    for (int i = 1; i < n; i++)
        jc[i] = jc[i - 1] * i % mod;
    ijc[n - 1] = inv(jc[n - 1]); 
    for (int i = n - 2; i >= 0; i--)
        ijc[i] = ijc[i + 1] * (i + 1) % mod;
}

ll C(int n, int k)
{
    if (k < 0 || k > n)
        return 0;
    return jc[n] * ijc[k] % mod * ijc[n - k] % mod;
}

ll P(int n, int k)
{
    if (k < 0 || k > n)
        return 0;
    return jc[n] * ijc[n - k] % mod;
}

cpp

lll

ostream &operator<<(ostream &os, lll n)
{
    if (n == 0)
        return os << 0;
    string s;
    while (n > 0)
    {
        s += char('0' + n % 10);
        n /= 10;
    }
    reverse(s.begin(), s.end());
    return os << s;
}

cpp

sieve&minp

vector<int> eulerSieve(int n)
{
    vector<char> isPrime(n + 1, 1); // 标记数组，初始全部设为true
    vector<int> primes;             // 存储筛选出的质数

    isPrime[0] = isPrime[1] = 0; // 0和1不是质数

    for (int i = 2; i <= n; ++i)
    {
        if (isPrime[i])
        {
            primes.push_back(i); // i是质数，加入质数列表
        }

        // 用当前已得到的质数去筛i的倍数
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j)
        {
            isPrime[i * primes[j]] = 0; // 标记i*primes[j]为非质数

            // 关键步骤：保证每个合数只被它的最小质因数筛掉
            if (i % primes[j] == 0)
            {
                break;
            }
        }
    }

    return primes;
}



// 线性处理所有数字的最小质因子
template <typename T>
vector<T> preprocess_min_prime(T n)
{
    vector<T> min_prime(n + 1); // 存储最小质因子
    vector<T> primes;           // 存储所有质数

    // 初始化，所有数的最小质因子设为自身
    for (T i = 0; i <= n; i++)
    {
        min_prime[i] = i;
    }

    // 线性筛法
    for (T i = 2; i <= n; i++)
    {
        if (min_prime[i] == i)
        { // i 是质数
            primes.push_back(i);
        }

        // 用当前质数 primes[j] 去筛合数
        for (size_t j = 0; j < primes.size(); j++)
        {
            T p = primes[j];
            if (p * i > n)
                break; // 超过范围，退出

            min_prime[p * i] = p; // 标记合数 p*i 的最小质因子为 p

            if (i % p == 0)
            { // 保证每个合数只被最小质因子筛一次
                break;
            }
        }
    }

    return min_prime;
}

cpp

umap hash

struct chash
{
    template <typename T1, typename T2>
    std::size_t operator()(const std::pair<T1, T2> &p) const
    {
        auto hash1 = std::hash<T1>{}(p.first);
        auto hash2 = std::hash<T2>{}(p.second);
        return hash1 ^ (hash2 << 2);
    }
};

struct chash
{
    std::size_t operator()(const std::array<int, 2> &arr) const { return std::hash<int>{}(arr[0]) ^ (std::hash<int>{}(arr[1]) << 2); }
};

cpp

zmod

using i64 = long long;

template <class T>
constexpr T fpow(T n, i64 k)
{
    T r = 1;
    for (; k; k >>= 1, n *= n)
        if (k & 1)
            r *= n;
    return r;
}

template <int MOD>
struct Zmod
{
    int x;

    constexpr Zmod(int x = 0) : x(norm(x % MOD)) {}

    static constexpr int norm(int x)
    {
        if (x < 0) x += MOD;
        if (x >= MOD) x -= MOD;
        return x;
    }

    constexpr int val() const { return x; }

    constexpr Zmod operator-() const
    {
        return Zmod(MOD - x);
    }

    constexpr Zmod inv() const
    {
        assert(x != 0);
        return fpow(*this, MOD - 2);
    }

    /* IO */
    friend std::istream &operator>>(std::istream &in, Zmod &a)
    {
        int v;
        in >> v;
        a = Zmod(v);
        return in;
    }

    friend std::ostream &operator<<(std::ostream &out, const Zmod &a)
    {
        return out << a.val();
    }

    /* 自增自减 */
    constexpr Zmod &operator++() { return x = norm(x + 1), *this; }
    constexpr Zmod &operator--() { return x = norm(x - 1), *this; }

    /* 复合赋值 */
    constexpr Zmod &operator+=(const Zmod &o)
    {
        x = norm(x + o.x);
        return *this;
    }

    constexpr Zmod &operator-=(const Zmod &o)
    {
        x = norm(x - o.x);
        return *this;
    }

    constexpr Zmod &operator*=(const Zmod &o)
    {
        x = (i64)x * o.x % MOD;
        return *this;
    }

    constexpr Zmod &operator/=(const Zmod &o)
    {
        return *this *= o.inv();
    }

    /* 二元运算 */
    friend constexpr Zmod operator+(Zmod a, const Zmod &b) { return a += b; }
    friend constexpr Zmod operator-(Zmod a, const Zmod &b) { return a -= b; }
    friend constexpr Zmod operator*(Zmod a, const Zmod &b) { return a *= b; }
    friend constexpr Zmod operator/(Zmod a, const Zmod &b) { return a /= b; }

    /* 比较 */
    friend constexpr bool operator==(const Zmod &a, const Zmod &b) { return a.x == b.x; }
    friend constexpr bool operator!=(const Zmod &a, const Zmod &b) { return a.x != b.x; }
    friend constexpr bool operator<(const Zmod &a, const Zmod &b) { return a.x < b.x; }
    friend constexpr bool operator>(const Zmod &a, const Zmod &b) { return a.x > b.x; }
};

constexpr int MOD[] = {998244353, 1000000007};
using Z = Zmod<MOD[0]>;

/* 示例：2^n */
Z power(int n)
{
    return fpow(Z(2), n);
}

cpp

三分

int l = 1, r = 1e9, ans = inf;
while (r - l > 3)
{
    int m1 = l + (r - l) / 3;
    int m2 = r - (r - l) / 3;
    if (calc(m1, i) >= calc(m2, i))
        l = m1;
    else
        r = m2;
}
for (int j = l; j <= r; j++)
    ans = min(ans, calc(j, i));

cpp

取模类

using i64 = long long;

template <class T>
constexpr T mypow(T n, i64 k)
{
    T r = 1;
    for (; k; k /= 2, n *= n)
    {
        if (k % 2)
        {
            r *= n;
        }
    }
    return r;
}

template <int MOD>
struct Zmod
{
    int x;
    Zmod(int x = 0) : x(norm(x % MOD)) {}

    constexpr int norm(int x) const
    {
        if (x < 0)
        {
            x += MOD;
        }
        if (x >= MOD)
        {
            x -= MOD;
        }
        return x;
    }
    constexpr int val() const
    {
        return x;
    }
    constexpr Zmod operator-() const
    {
        Zmod val = norm(MOD - x);
        return val;
    }
    constexpr Zmod inv() const
    {
        assert(x != 0);
        return mypow(*this, MOD - 2);
    }
    friend constexpr auto &operator>>(istream &in, Zmod &j)
    {
        int v;
        in >> v;
        j = Zmod(v);
        return in;
    }
    friend constexpr auto &operator<<(ostream &o, const Zmod &j)
    {
        return o << j.val();
    }
    constexpr Zmod &operator++()
    {
        x = norm(x + 1);
        return *this;
    }
    constexpr Zmod &operator--()
    {
        x = norm(x - 1);
        return *this;
    }
    constexpr Zmod &operator+=(const Zmod &i)
    {
        x = norm(x + i.x);
        return *this;
    }
    constexpr Zmod &operator-=(const Zmod &i)
    {
        x = norm(x - i.x);
        return *this;
    }
    constexpr Zmod &operator*=(const Zmod &i)
    {
        x = i64(x) * i.x % MOD;
        return *this;
    }
    constexpr Zmod &operator/=(const Zmod &i)
    {
        return *this *= i.inv();
    }
    constexpr Zmod &operator%=(const int &i)
    {
        return x %= i, *this;
    }
    friend constexpr Zmod operator+(const Zmod i, const Zmod j)
    {
        return Zmod(i) += j;
    }
    friend constexpr Zmod operator-(const Zmod i, const Zmod j)
    {
        return Zmod(i) -= j;
    }
    friend constexpr Zmod operator*(const Zmod i, const Zmod j)
    {
        return Zmod(i) *= j;
    }
    friend constexpr Zmod operator/(const Zmod i, const Zmod j)
    {
        return Zmod(i) /= j;
    }
    friend constexpr Zmod operator%(const Zmod i, const int j)
    {
        return Zmod(i) %= j;
    }
    friend constexpr bool operator==(const Zmod i, const Zmod j)
    {
        return i.val() == j.val();
    }
    friend constexpr bool operator!=(const Zmod i, const Zmod j)
    {
        return i.val() != j.val();
    }
    friend constexpr bool operator<(const Zmod i, const Zmod j)
    {
        return i.val() < j.val();
    }
    friend constexpr bool operator>(const Zmod i, const Zmod j)
    {
        return i.val() > j.val();
    }
};

constexpr int MOD[] = {998244353, 1000000007};
using Z = Zmod<MOD[0]>;

Z power(int n)
{
    return mypow(Z(2), n);
}

cpp

random

static random_device rd;
static mt19937 g(rd());

shuffle(a.begin() + 1, a.end(), g); // 随机打乱数组

uniform_real_distribution<double> dist01(0.0, 1.0); // [0,1)
uniform_real_distribution<double> dist11(-1.0, 1.0); // [-1,1)

cpp

字符串

KMP

// 在文本串 txt 中查找模式串 ptn，返回所有成功匹配的位置（ptn[0] 在 txt 中的下标）
vector<int> kmp(const string &txt, const string &ptn)
{
    int n = ptn.size();
    vector<int> pi(n);
    int cnt = 0;
    for (int i = 1; i < n; i++)
    {
        char b = ptn[i];
        while (cnt && ptn[cnt] != b)
            cnt = pi[cnt - 1];
        if (ptn[cnt] == b)
            cnt++;
        pi[i] = cnt;
    }

    vector<int> pos;
    cnt = 0;
    for (int i = 0; i < txt.size(); i++)
    {
        char b = txt[i];
        while (cnt && ptn[cnt] != b)
            cnt = pi[cnt - 1];
        if (ptn[cnt] == b)
            cnt++;
        if (cnt == n)
        {
            pos.pb(i - n + 1);
            cnt = pi[cnt - 1];
        }
    }
    return pos;
}

cpp

z函数

z[i] = 字符串 s 和以位置 i 开头的后缀的最长公共前缀(LCP) 的长度

 vector<int> calc_z(const string &s)
 {
    int n = s.size();
    vector<int> z(n);
    int box_l = 0, box_r = 0;
    for (int i = 1; i < n; i++)
    {
        if (i <= box_r)
            z[i] = min(z[i - box_l], box_r - i + 1);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
        {
            box_l = i;
            box_r = i + z[i];
            z[i]++;
        }
    }
    z[0] = n;
    return z;
 }

cpp

Manacher

// 函数：计算字符串的最长回文子串长度（Manacher算法）
int manacher(const string& str) {
    // 如果输入字符串为空，直接返回0
    if (str.empty()) return 0;
    
    // 构建预处理字符串，插入特殊字符避免奇偶长度问题
    string s = "$#";
    for (char c : str) {
        s += c;
        s += '#';
    }
    s += '&';
    
    int n = s.length();
    vector<int> p(n, 0);  // p[i]表示以i为中心的最长回文半径
    
    int center = 0;  // 当前回文串的中心
    int right = 0;   // 当前回文串的右边界
    int maxLen = 0;  // 最长回文半径
    
    for (int i = 1; i < n - 1; i++) {
        // 利用对称性初始化p[i]
        if (i < right) {
            p[i] = min(p[2 * center - i], right - i);
        } else {
            p[i] = 1;
        }
        
        // 中心扩展
        while (s[i + p[i]] == s[i - p[i]]) {
            p[i]++;
        }
        
        // 更新当前最右回文边界
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
        
        // 更新最大回文半径
        maxLen = max(maxLen, p[i]);
    }
    
    // 原始字符串中的最长回文子串长度 = 处理字符串中的最大半径 - 1
    return maxLen - 1;
}

cpp

AC自动机

struct ahocorasick
{
    static constexpr int sz = 26;
    struct node
    {
        int len;
        int link;
        array<int, sz> next;
        node() : len{0}, link{0}, next{} {}
    };
    vec<node> t;

    void init()
    {
        t.assign(2, node());
        t[0].next.fill(1);
        t[0].len = -1;
    }

    ahocorasick() { init(); };

    int newnode()
    {
        t.emplace_back();
        return t.size() - 1;
    }

    void add(const string &a)
    {
        int p = 1;
        for (auto c : a)
        {
            int x = c - 'a';
            if (t[p].next[x] == 0)
            {
                t[p].next[x] = newnode();
                t[t[p].next[x]].len = t[p].len + 1;
            }
            p = t[p].next[x];
        }
    }

    void work()
    {
        queue<int> q;
        q.push(1);
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            for (int i = 0; i < sz; i++)
            {
                if (t[x].next[i] == 0)
                    t[x].next[i] = t[t[x].link].next[i];
                else
                {
                    t[t[x].next[i]].link = t[t[x].link].next[i];
                    q.push(t[x].next[i]);
                }
            }
        }
    }

    int next(int p, int x) { return t[p].next[x]; }
    int link(int p) { return t[p].link; }
    int len(int p) { return t[p].len; }
    int size() { return t.size(); }
};

cpp

图论

Tarjan

struct SCC
{
    int n, now, cnt;
    vector<vector<int>> ver;
    vector<int> dfn, low, col, S;

    SCC(int n) : n(n), ver(n + 1), low(n + 1)
    {
        dfn.resize(n + 1, -1);
        col.resize(n + 1, -1);
        now = cnt = 0;
    }

    void add(int x, int y) { ver[x].push_back(y); }

    void tarjan(int x)
    {
        dfn[x] = low[x] = now++;
        S.push_back(x);
        for (auto y : ver[x])
        {
            if (dfn[y] == -1)
            {
                tarjan(y);
                low[x] = min(low[x], low[y]);
            }
            else if (col[y] == -1)
                low[x] = min(low[x], dfn[y]);
        }
        if (dfn[x] == low[x])
        {
            int pre;
            cnt++;
            do
            {
                pre = S.back();
                col[pre] = cnt;
                S.pop_back();
            } while (pre != x);
        }
    }

    tuple<int, vec<vec<int>>, vec<int>> work()
    {                                // [cnt 新图的顶点数量]
        for (int i = 1; i <= n; i++) // 避免图不连通
            if (dfn[i] == -1)
                tarjan(i);

        vector<vector<int>> adj(cnt + 1);
        for (int i = 1; i <= n; i++)
        {
            for (auto j : ver[i])
            {
                int x = col[i], y = col[j];
                if (x != y)
                    adj[x].push_back(y);
            }
        }
        return {cnt, adj, col};
    }
};

cpp

LCA

树上倍增

void cold_beans()
{
    int n, m, s;
    cin >> n >> m >> s;
    vec<vec<int>> g(n + 1), st(20, vec<int>(n + 1));
    vec<int> dep(n + 1);
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    auto dfs = [&](this auto &&dfs, int u, int fa, int d) -> void
    {
        st[0][u] = fa;
        dep[u] = d;
        for (auto v : g[u])
        {
            if (v == fa)
                continue;
            dfs(v, u, d + 1);
        }
    };
    dfs(s, 0, 1);
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= n; j++)
            st[i][j] = st[i - 1][st[i - 1][j]];
    auto lca = [&](int a, int b) -> int
    {
        if (dep[a] < dep[b])
            swap(a, b);
        int wt = dep[a] - dep[b];
        for (int i = 0; i < 20; i++)
            if (wt & 1 << i)
                a = st[i][a];
        if (a == b)
            return a;
        for (int i = 19; i >= 0; i--)
        {
            if (dep[a] > 1 << i && st[i][a] != st[i][b])
                a = st[i][a], b = st[i][b];
        }
        return st[0][a];
    };
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }
}

cpp

Tarjan

struct DSU
{
    vector<int> fa, p;

    DSU(int n)
    {
        fa.resize(n + 1);
        iota(fa.begin(), fa.end(), 0);
        p.resize(n + 1, 1);
    }
    
    int get(int x)
    {
        while (x != fa[x])
            x = fa[x] = fa[fa[x]];
        return x;
    }
    
    bool merge(int from, int to)
    {
        from = get(from), to = get(to);
        if (from == to) return false;
        fa[from] = to;
        p[to] += p[from];
        return true;
    }
    
    bool same(int x, int y)
    {
        return get(x) == get(y);
    }
    
    int size(int x)
    {
        return p[get(x)];
    }
};

void cold_beans()
{
    int n, m, s;
    cin >> n >> m >> s;
    vec<vec<int>> g(n + 1);
    vec<int> ans(m + 1);
    vec<char> vis(n + 1);
    vec<vec<aii>> q(n + 1);
    DSU dsu(n + 1);
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        q[a].pb({b, i});
        q[b].pb({a, i});
    }
    auto dfs = [&](this auto &&dfs, int u, int fa) -> void
    {
        vis[u] = 1;
        for (auto v : g[u])
        {
            if (v == fa)
                continue;
            dfs(v, u);
            dsu.merge(v, u);
        }
        for (auto &[v, num] : q[u])
            if (vis[v])
                ans[num] = dsu.get(v);
    };
    dfs(s, 0);
    for (int i = 1; i <= m; i++)
        cout << ans[i] << endl;
}

cpp

Hierholzer

有向图

    vec<int> ans;//有向图，倒序输出ans得到路径。如果需要字典序最小的路径,把g中的vec改pq，back改top

    auto dfs = [&](this auto &&dfs, int u) -> void
    {
        while (!g[u].empty())
        {
            int v = g[u].back();
            g[u].pop();
            dfs(v);
        }
        ans.pb(u);
    };

cpp

无向图

//如果不需要字典序最小可以把pq换成vec
vec<char> vis(m + 1);
vec<priority_queue<aii, vec<aii>, greater<aii>>> g(501);
vec<int> ans;

auto dfs = [&](this auto &&dfs, int u) -> void
{
    while (!g[u].empty())
    {
        auto [v, i] = g[u].top();
        g[u].pop();
        if (!vis[i])
        {
            vis[i] = 1;
            dfs(v);
        }
    }
    ans.pb(u);
};

cpp

Dijkstra

vec<int> dis(n + 1, inf);
vec<char> vis(n + 1);
priority_queue<aii, vec<aii>, greater<aii>> q;
int s = 1;
q.push({0, s});
dis[s] = 0;
while (!q.empty())
{
    auto [w, v] = q.top();
    q.pop();
    if (vis[v])
        continue;
    vis[v] = 1;
    for (auto &[nv, nw] : g[v])
    {
        if (dis[nv] > dis[v] + nw)
        {
            dis[nv] = dis[v] + nw;
            q.push({dis[nv], nv});
        }
    }
}

cpp

kruskal

struct DSU
{
    int n;
    vector<int> fa, size;
    DSU(int a = 0) { init(a); }
    void init(int a)
    {
        n = a;
        fa.assign(n + 1, 0);
        size.assign(n + 1, 1);
        for (int i = 1; i <= n; i++)
            fa[i] = i;
    }

    int find(int x)
    {
        if (x != fa[x])
            fa[x] = find(fa[x]);
        return fa[x];
    }

    bool merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x == y)
            return 0;
        if (size[x] < size[y])
            swap(x, y);
        size[x] += size[y];
        fa[y] = x;
        return 1;
    }

    bool same(int a, int b) { return find(a) == find(b); }

    int sz(int a) { return size[find(a)]; }
};

void Thirstarfish()
{
    int n, m, x, y, z;
    cin >> n >> m;
    DSU dsu(n);
    vector<tiii> q;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        q.pb({z, x, y});
    }
    sort(q.begin(), q.end());
    int cnt = 0, ans = 0;
    for (auto &[w, u, v] : q)
    {
        if (dsu.same(u, v))
            continue;
        ans += w;
        cnt++;
        dsu.merge(u, v);
        if (cnt == n - 1)
            break;
    }
    if (cnt != n - 1)
        cout << "orz" << endl;
    else
        cout << ans << endl;
}

cpp

HK

struct HK
{
    int n, m;
    vec<vec<int>> g;
    vec<int> ti, rec;
    HK(int _n, int _m) : n(_n), m(_m)
    {
        g.resize(n + 1);
        ti.resize(n + 1);
        rec.resize(m + 1);
    }

    bool dfs(int u, int t)
    {
        if (ti[u] == t)
            return 0;
        ti[u] = t;
        for (auto v : g[u])
        {
            if (!rec[v] || dfs(rec[v], t))
            {
                rec[v] = u;
                return 1;
            }
        }
        return 0;
    }

    void add(int x, int y)
    {
        g[x].pb(y);
    }

    int work()
    {
        int ans = 0;
        for (int i = 1; i <= n; i++)
            ans += dfs(i, i);
        return ans;
    }
};

cpp

网络流

Dinic

struct dinic
{
    int n;
    vec<vec<int>> g;
    vec<aii> e;
    vec<int> dis, cur;

    dinic(int _n)
    {
        n = _n;
        g.resize(n + 1);
    }

    void add(int u, int v, int w)
    {
        g[u].pb(e.size());
        e.pb({v, w});
        g[v].pb(e.size());
        e.pb({u, 0});
    }

    bool bfs(int s, int t)
    {
        dis.assign(n + 1, -1);
        queue<int> q;
        dis[s] = 0;
        q.push(s);
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto i : g[u])
            {
                auto &[v, c] = e[i];
                if (c > 0 && dis[v] == -1)
                {
                    dis[v] = dis[u] + 1;
                    if (v == t)
                        return true;
                    q.push(v);
                }
            }
        }
        return false;
    }

    int dfs(int u, int t, int f)
    {
        if (u == t)
            return f;
        int r = f;
        for (int &i = cur[u]; i < (int)(g[u].size()); i++)
        {
            int j = g[u][i];
            auto &[v, c] = e[j];
            if (c > 0 && dis[v] == dis[u] + 1)
            {
                int temp = dfs(v, t, min(r, c));
                e[j][1] -= temp;
                e[j ^ 1][1] += temp;
                r -= temp;
                if (r == 0)
                    return f;
            }
        }
        return f - r;
    }

    int work(int s, int t)
    {
        int ans = 0;
        while (bfs(s, t))
        {
            cur.assign(n + 1, 0);
            ans += dfs(s, t, inf);
        }
        return ans;
    }

    vec<a4i> edge() // from/to/flow/cap
    {
        vec<a4i> ret;
        for (int i = 0; i < e.size(); i += 2)
            ret.pb({e[i ^ 1][0], e[i][0], e[i ^ 1][1], e[i ^ 1][1] + e[i][1]});
        return ret;
    }

    // 返回残量网络中从 s 可达的点
    vec<char> reachable(int s)
    {
        vec<char> vis(n + 1, 0);
        queue<int> q;
        q.push(s);
        vis[s] = 1;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (auto id : g[u])
            {
                auto &[v, c] = e[id];
                if (c > 0 && !vis[v])
                {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
        return vis;
    }
};

cpp

mcmf

正费用

struct mcmf
{
    vec<aiii> e; // to,cap,cost
    vec<vec<int>> g;
    vec<int> h, dis, pre;
    int n;
    mcmf(int _n)
    {
        n = _n;
        g.resize(n + 1);
        h.resize(n + 1);
    }

    void add(int u, int v, int w, int c)
    {
        g[u].pb(e.size());
        e.pb({v, w, c});
        g[v].pb(e.size());
        e.pb({u, 0, -c});
    }

    bool dijkstra(int s, int t)
    {
        dis.assign(n + 1, inf);
        pre.assign(n + 1, -1);
        priority_queue<aii, vec<aii>, greater<aii>> q;
        dis[s] = 0;
        q.push({0, s});
        while (!q.empty())
        {
            auto [d, u] = q.top();
            q.pop();
            if (dis[u] != d)
                continue;
            for (auto i : g[u])
            {
                auto &[v, w, c] = e[i];
                if (w > 0 && dis[v] > d + h[u] - h[v] + c)
                {
                    dis[v] = d + h[u] - h[v] + c;
                    pre[v] = i;
                    q.push({dis[v], v});
                }
            }
        }
        return dis[t] != inf;
    }

    aii work(int s, int t)
    {
        aii ret = {0, 0}; // flow,cost
        while (dijkstra(s, t))
        {
            for (int i = 1; i <= n; i++)
                h[i] += dis[i];
            int aug = inf;
            for (int i = t; i != s; i = e[pre[i] ^ 1][0])
                aug = min(aug, e[pre[i]][1]);
            for (int i = t; i != s; i = e[pre[i] ^ 1][0])
            {
                e[pre[i]][1] -= aug;
                e[pre[i] ^ 1][1] += aug;
            }
            ret[0] += aug;
            ret[1] += aug * h[t];
        }
        return ret;
    }
};

cpp

负费用

struct mcmf
{
    vec<aiii> e; // to,cap,cost
    vec<vec<int>> g;
    vec<int> h, dis, pre;
    int n;
    mcmf(int _n)
    {
        n = _n;
        g.resize(n + 1);
        h.resize(n + 1);
    }

    void add(int u, int v, int w, int c)
    {
        g[u].pb(e.size());
        e.pb({v, w, c});
        g[v].pb(e.size());
        e.pb({u, 0, -c});
    }

    bool spfa(int s, int t)
    {
        dis.assign(n + 1, inf);
        pre.assign(n + 1, -1);
        vec<char> inq(n + 1, 0);
        queue<int> q;
        dis[s] = 0;
        q.push(s);
        inq[s] = 1;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for (auto i : g[u])
            {
                auto &[v, w, c] = e[i];
                if (w > 0 && dis[v] > dis[u] + c)
                {
                    dis[v] = dis[u] + c;
                    pre[v] = i;
                    if (!inq[v])
                    {
                        q.push(v);
                        inq[v] = 1;
                    }
                }
            }
        }
        return dis[t] != inf;
    }

    bool dijkstra(int s, int t)
    {
        dis.assign(n + 1, inf);
        pre.assign(n + 1, -1);
        priority_queue<aii, vec<aii>, greater<aii>> q;
        dis[s] = 0;
        q.push({0, s});
        while (!q.empty())
        {
            auto [d, u] = q.top();
            q.pop();
            if (dis[u] != d)
                continue;
            for (auto i : g[u])
            {
                auto &[v, w, c] = e[i];
                if (w > 0 && dis[v] > d + h[u] - h[v] + c)
                {
                    dis[v] = d + h[u] - h[v] + c;
                    pre[v] = i;
                    q.push({dis[v], v});
                }
            }
        }
        return dis[t] != inf;
    }

    aii work(int s, int t)
    {
        aii ret = {0, 0};
        if (!spfa(s, t))
            return ret;
        for (int i = 1; i <= n; i++)
            if (dis[i] < inf)
                h[i] = dis[i];
        while (1)
        {
            int aug = inf;
            for (int i = t; i != s; i = e[pre[i] ^ 1][0])
                aug = min(aug, e[pre[i]][1]);
            for (int i = t; i != s; i = e[pre[i] ^ 1][0])
            {
                e[pre[i]][1] -= aug;
                e[pre[i] ^ 1][1] += aug;
            }
            ret[0] += aug;
            ret[1] += aug * h[t];
            if (!dijkstra(s, t))
                break;
            for (int i = 1; i <= n; i++)
                if (dis[i] < inf)
                    h[i] += dis[i];
        }
        return ret;
    }
};

cpp

DP

数位dp

单lim

class Solution
{
public:
    int countLargestGroup(int nn)
    {
        string s = to_string(nn);
        int n = s.size();
        vec dp(n, vec<int>(9 * n + 1, -1));
        auto dfs = [&](this auto &&dfs, int wei, int left, bool lim) -> int
        {
            if (wei == n)
                return left == 0;
            if (!lim && dp[wei][left] != -1)
                return dp[wei][left];
            int ran = lim ? s[wei] - '0' : 9;
            int res = 0;
            for (int i = 0; i <= min(left, ran); i++)
                res += dfs(wei + 1, left - i, lim && i == ran);
            if (!lim)
                dp[wei][left] = res;
            return res;
        };
        int ans = 0, temp = 0;
        for (int i = 1; i <= 9 * n; i++)
        {
            int cal = dfs(0, i, 1);
            if (cal > temp)
                ans = 1, temp = cal;
            else if (cal == temp)
                ans++;
        }
        return ans;
    }
};

cpp

双lim

class Solution
{
public:
    int countBalls(int lowLimit, int highLimit)
    {
        string num1 = to_string(lowLimit), num2 = to_string(highLimit);
        int n = num2.size();
        num1.insert(num1.begin(), n - num1.size(), '0');
        vec dp(n, vec<int>(9 * n + 1, -1));
        auto dfs = [&](this auto &&dfs, int wei, int sum, bool limit_low, bool limit_high) -> int
        {
            if (sum < 0)
                return 0;
            if (wei == n)
                return sum == 0;
            if (!limit_low && !limit_high && dp[wei][sum] != -1)
                return dp[wei][sum];
            int lo = limit_low ? num1[wei] - '0' : 0;
            int hi = limit_high ? num2[wei] - '0' : 9;
            int res = 0;
            for (int i = lo; i <= hi; i++)
                res = (res + dfs(wei + 1, sum - i, limit_low && i == lo, limit_high && i == hi)) % mod;
            if (!limit_low && !limit_high)
                dp[wei][sum] = res;
            return res;
        };
        int ans = 0;
        for (int i = 1; i <= 9 * n; i++)
        {
            int cal = dfs(0, i, 1, 1);
            ans = max(ans, cal);
        }
        return ans;
    }
};

cpp

双lim+前导零

void Thirstarfish()
{
    int l, r;
    cin >> l >> r;
    int n = 63 - clz(r);
    vec dp(n + 1, vec<int>(2 * n + 1, -1));
    auto dfs = [&](this auto &&dfs, int wei, int sum, bool lml, bool lmh, bool lead) -> int
    {
        if (wei < 0)
            return sum >= n;
        if (!lml && !lmh && !lead && dp[wei][sum] != -1)
            return dp[wei][sum];
        int lo = lml ? (l >> wei & 1) : 0;
        int hi = lmh ? (r >> wei & 1) : 1;
        int res = 0;
        for (int i = lo; i <= hi; i++)
            if (lead && i == 0)
                res += dfs(wei - 1, sum, lml && i == lo, lmh && i == hi, 1);
            else
                res += dfs(wei - 1, i == 0 ? sum + 1 : sum - 1, lml && i == lo, lmh && i == hi, lead && i != 1);
        if (!lml && !lmh && !lead)
            dp[wei][sum] = res;
        return res;
    };
    cout << dfs(n, n, 1, 1, 1) << endl;
}

cpp

数学

高斯消元

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define vec vector
#define fir first
#define sec second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mxe max_element
#define mne min_element
#define ppc __builtin_popcount
#define ctz __builtin_ctzll
#define clz __builtin_clzll
#define pcs(n) cout << fixed << setprecision(n)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef unsigned long long ull;
typedef __int128_t lll;
const int mod = 998244353;
const int N = 200005;
const int inf = 0x3f3f3f3f3f3f3f;
const int bs = 433;
const int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
const double eps = 1e-8;

// 高斯消元法解线性方程组
int gauss(vector<vector<double>> &a)
{
    int n = a.size();
    int c, r;
    for (c = 0, r = 0; c < n; c++)
    {
        int t = r;
        // 找到当前列绝对值最大的行
        for (int i = r; i < n; i++)
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;
        if (fabs(a[t][c]) < eps)
            continue;

        // 将绝对值最大的行换到最顶端
        for (int i = c; i <= n; i++)
            swap(a[t][i], a[r][i]);

        // 将当前行的首位变成1
        for (int i = n; i >= c; i--)
            a[r][i] /= a[r][c];

        // 用当前行将下面所有的列消成0
        for (int i = r + 1; i < n; i++)
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j--)
                    a[i][j] -= a[r][j] * a[i][c];
        r++;
    }
    if (r < n)
    {
        for (int i = r; i < n; i++)
            if (fabs(a[i][n]) > eps)
                return -1; // 无解
        return 0;          // 无穷多解
    }
    // 回代求解
    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            a[i][n] -= a[i][j] * a[j][n];
    return 1; // 有唯一解
}

void Thirstarfish()
{
    int n;
    cin >> n;
    vector<vector<double>> a(n, vector<double>(n + 1));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n + 1; j++)
            cin >> a[i][j];
    int res = gauss(a);
    if (res == -1)
        cout << -1 << endl;
    else if (res == 0)
        cout << 0 << endl;
    else
    {
        pcs(2);
        for (int i = 0; i < n; i++)
            cout << "x" << i + 1 << "=" << a[i][n] << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    // cin >> _; // 如果是单测记得注释掉这一行
    while (_--)
        Thirstarfish();
    return 0;
}

cpp

拉格朗日插值

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define vec vector
#define fir first
#define sec second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define mxe max_element
#define mne min_element
#define ppc __builtin_popcount
#define ctz __builtin_ctzll
#define clz __builtin_clzll // 二进制前导零的个数
#define pcs(n) cout << fixed << setprecision(n)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef unsigned long long ull;
typedef __int128_t lll;
const int mod = 998244353;
const int N = 200005;
const int inf = 0x3f3f3f3f3f3f3f3f;
const int bs = 433;
const int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};

ll fast_pow(ll a, ll b)
{
    ll ans = 1;
    a %= mod; // 先取模，防止a过大
    while (b)
    {
        if (b & 1)
        { // 等价于 b % 2
            ans = (ans * a) % mod;
        }
        b >>= 1; // 等价于 b /= 2
        a = (a * a) % mod;
    }
    return ans;
}

ll inv(int a, int b)
{
    return a * fast_pow(b, mod - 2) % mod;
}

void Thirstarfish()
{
    int n, k, _x, _y, ans = 0;
    cin >> n >> k;
    vec<int> x{0}, y{0};
    for (int i = 1; i <= n; i++)
    {
        cin >> _x >> _y;
        x.pb(_x);
        y.pb(_y);
    }
    for (int i = 1; i <= n; i++)
    {
        ll a = y[i], b = 1;
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                continue;
            a = a * (k - x[j]) % mod;
            b = b * (x[i] - x[j]) % mod;
        }
        ans = (ans + inv(a, b)) % mod;
    }
    cout << (ans + mod) % mod << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    // cin >> _; // 如果是单测记得注释掉这一行
    while (_--)
        Thirstarfish();
    return 0;
}

cpp

矩阵快速幂

固定大小

const int SIZE = 100;

using Matrix = array<array<int, SIZE>, SIZE>;

// 返回矩阵 a 和矩阵 b 相乘的结果
Matrix mul(Matrix &a, Matrix &b)
{
    Matrix c{};
    for (int i = 0; i < SIZE; i++)
        for (int k = 0; k < SIZE; k++)
        {
            if (a[i][k] == 0)
                continue;
            for (int j = 0; j < SIZE; j++)
                c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]) % mod;
        }
    return c;
}

// 返回 n 个矩阵 a 相乘的结果
Matrix pow(Matrix a, int n)
{
    Matrix res = {};
    for (int i = 0; i < SIZE; i++)
        res[i][i] = 1; // 单位矩阵
    while (n)
    {
        if (n & 1)
            res = mul(res, a);
        a = mul(a, a);
        n >>= 1;
    }
    return res;
}

cpp

不固定大小

// 使用vector代替固定大小的array
using Matrix = vector<vector<int>>;

// 返回矩阵 a 和矩阵 b 相乘的结果
Matrix mul(Matrix &a, Matrix &b) {
    int n = a.size();      // 行数
    int m = b[0].size();   // 列数
    int p = b.size();      // 中间维度
    
    Matrix c(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < p; k++) {
            if (a[i][k] == 0)
                continue;
            for (int j = 0; j < m; j++)
                c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]) % mod;
        }
    return c;
}

// 返回 n 个矩阵 a 相乘的结果
Matrix pow(Matrix a, int n) {
    int size = a.size();
    Matrix res(size, vector<int>(size, 0));
    
    // 单位矩阵
    for (int i = 0; i < size; i++)
        res[i][i] = 1;
    
    while (n) {
        if (n & 1)
            res = mul(res, a);
        a = mul(a, a);
        n >>= 1;
    }
    return res;
}

cpp

树有关结论

对于给定度数为 $d_1,d_2,…,d_n$ 的一棵无根树拥有的情况数： $\prod_{i=1}^{n} \frac{(d_i - 1)!}{(n-2)!}$

对于给定节点数的无根树拥有的情况数： $n^{n-1}$

斯特林数结论

第一类斯特林数

上升幂展开为普通幂： $x^{\overline{n}} = \sum_{k=0}^{n} {n \brack k} x^k$

下降幂展开为普通幂： $x^{\underline{n}} = \sum_{k=0}^{n} s(n,k) x^k$

带符号与无符号关系： $s(n,k) = (-1)^{n-k} {n \brack k}$

第二类斯特林数

普通幂展开为下降幂： $x^n = \sum_{k=0}^{n} {n \brace k} x^{\underline{k}}$

斯特林数显式公式： ${n \brace k} = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$

两类斯特林数关系

普通幂与下降幂互相表示： $x^n = \sum_{k} S(n,k) x^{\underline{k}}$

$x^{\underline{n}} = \sum_{k} s(n,k) x^k$

数据结构

DSU

struct DSU
{
    int n;
    vector<int> fa, size;
    DSU(int a = 0) { init(a); }
    void init(int a)
    {
        n = a;
        fa.assign(n + 1, 0);
        size.assign(n + 1, 1);
        for (int i = 1; i <= n; i++)
            fa[i] = i;
    }

    int find(int x)
    {
        if (x != fa[x])
            fa[x] = find(fa[x]);
        return fa[x];
    }

    bool merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x == y)
            return 0;
        if (size[x] < size[y])
            swap(x, y);
        size[x] += size[y];
        fa[y] = x;
        return 1;
    }

    bool same(int a, int b) { return find(a) == find(b); }

    int sz(int a) { return size[find(a)]; }
};

cpp

BIT

单点1D

struct BIT
{
    int n, lg;
    vector<int> w;

    BIT(int _n)
    {
        n = _n;
        w.resize(n + 1);
        lg = __lg(n);
    }

    void add(int x, int k)
    {
        for (; x <= n; x += x & -x)
            w[x] += k;
    }

    int ask(int x)
    {
        if (x == 0)
            return 0;
        int ans = 0;
        for (; x; x -= x & -x)
            ans += w[x];
        return ans;
    }

    int ask(int x, int y)
    {
        if (x == 1)
            return ask(y);
        return ask(y) - ask(x - 1);
    }

    int kth(int k)
    {
        int pos = 0;
        for (int i = 1 << lg; i; i >>= 1)
        {
            int nxt = pos + i;
            if (nxt <= n && w[nxt] < k)
            {
                k -= w[nxt];
                pos = nxt;
            }
        }
        return pos + 1;
    }
};

cpp

区间2D

template <class T>
struct BIT_2D
{
    int n, m;
    vector<vector<T>> b1, b2, b3, b4;

    BIT_2D(int n, int m) : n(n), m(m)
    {
        b1.resize(n + 1, vector<T>(m + 1));
        b2.resize(n + 1, vector<T>(m + 1));
        b3.resize(n + 1, vector<T>(m + 1));
        b4.resize(n + 1, vector<T>(m + 1));
    }

    void matrixAdd(int x, int y, int X, int Y, T k)
    { // 区块修改：二维差分
        X++, Y++;
        auto add = [&](int x, int y, T k)
        {
            for (int i = x; i <= n; i += i & -i)
                for (int j = y; j <= m; j += j & -j)
                {
                    b1[i][j] += k;
                    b2[i][j] += k * (x - 1);
                    b3[i][j] += k * (y - 1);
                    b4[i][j] += k * (x - 1) * (y - 1);
                }
        };
        add(x, y, k);
        add(X, y, -k);
        add(x, Y, -k);
        add(X, Y, k);
    }

    T matrixSum(int x, int y, int X, int Y)
    { // 区块查询：二维前缀和
        x--, y--;
        auto ask = [&](int x, int y)
        {
            T ans = T();
            for (int i = x; i; i -= i & -i)
                for (int j = y; j; j -= j & -j)
                {
                    ans += x * y * b1[i][j];
                    ans -= y * b2[i][j];
                    ans -= x * b3[i][j];
                    ans += b4[i][j];
                }
            return ans;
        };
        return ask(X, Y) - ask(x, Y) - ask(X, y) + ask(x, y);
    }
};

cpp

Seg

lazy

template <typename T>
struct seg
{
    struct node
    {
        int l, r;
        T w, lazy;
        node operator+(const node &other) const
        {
            node res;
            res.l = l;
            res.r = other.r;
            res.w = w + other.w;
            res.lazy = 0;
            return res; // lazy不参与合并，重置为0
        }
    };
    vector<T> w;
    vector<node> t;

    inline int ls(int k) { return k << 1; }
    inline int rs(int k) { return k << 1 | 1; }

    seg(int n)
    {
        w.resize(n + 1);
        t.resize((n << 2) + 1);
        build(1, n);
    }

    seg(vector<T> in)
    {
        int n = in.size() - 1;
        w.resize(n + 1);
        for (int i = 1; i <= n; i++)
            w[i] = in[i];
        t.resize((n << 2) + 1);
        build(1, n);
    }

    inline void update(int k, T lazy)
    {
        t[k].w += (t[k].r - t[k].l + 1) * lazy;
        t[k].lazy += lazy;
    }

    inline void pushup(int k)
    {
        t[k] = t[ls(k)] + t[rs(k)];
    }

    inline void pushdown(int k)
    {
        if (t[k].lazy == 0)
            return;
        update(ls(k), t[k].lazy);
        update(rs(k), t[k].lazy);
        t[k].lazy = 0;
    }

    void build(int l, int r, int k = 1)
    {
        if (l == r)
        {
            t[k] = {l, r, w[l], 0};
            return;
        }
        t[k] = {l, r};
        int mid = l + r >> 1;
        build(l, mid, ls(k));
        build(mid + 1, r, rs(k));
        pushup(k);
    }

    void modify(int l, int r, T v, int k = 1)
    {
        if (l <= t[k].l && r >= t[k].r)
        {
            update(k, v);
            return;
        }
        pushdown(k);
        int mid = (t[k].l + t[k].r) >> 1;
        if (l <= mid)
            modify(l, r, v, ls(k));
        if (r > mid)
            modify(l, r, v, rs(k));
        pushup(k);
    }

    node queryNode(int l, int r, int k = 1)
    {
        if (l <= t[k].l && r >= t[k].r)
            return t[k];
        pushdown(k);
        int mid = (t[k].l + t[k].r) >> 1;
        if (r <= mid)
            return queryNode(l, r, ls(k));
        if (l > mid)
            return queryNode(l, r, rs(k));
        return queryNode(l, r, ls(k)) + queryNode(l, r, rs(k));
    }

    T query(int l, int r, int k = 1)
    {
        return queryNode(l, r, k).w;
    }
};

cpp

unlazified

template<typename T>
struct seg
{
    struct node
    {
        int l, r;
        T w;
        node operator+(const node &other) const
        {
            node res;
            res.l = l;
            res.r = other.r;
            res.w = w + other.w;
            return res; 
        }
    };

    vector<T> w;
    vector<node> t;

    inline int ls(int k) { return k << 1; }
    inline int rs(int k) { return k << 1 | 1; }

    seg(int n)
    {
        w.resize(n + 1);
        t.resize((n << 2) + 1);
        build(1, n);
    }

    seg(vector<T> in)
    {
        int n = in.size() - 1;
        w.resize(n + 1);
        for (int i = 1; i <= n; i++)
            w[i] = in[i];
        t.resize((n << 2) + 1);
        build(1, n);
    }

    inline void pushup(int k)
    {
        t[k] = t[ls(k)] + t[rs(k)];
    }

    void build(int l, int r, int k = 1)
    {
        if (l == r)
        {
            t[k] = {l, r, w[l]};
            return;
        }
        t[k] = {l, r};
        int mid = l + r >> 1;
        build(l, mid, ls(k));
        build(mid + 1, r, rs(k));
        pushup(k);
    }

    void modify(int pos, T v, int k = 1)
    {
        if (t[k].l == t[k].r)
        {
            t[k].w += v;
            return;
        }
        int mid = (t[k].l + t[k].r) >> 1;
        if (pos <= mid)
            modify(pos, v, ls(k));
        else
            modify(pos, v, rs(k));
        pushup(k);
    }

    node queryNode(int l, int r, int k = 1)
    {
        if (l <= t[k].l && r >= t[k].r)
            return t[k];
        int mid = (t[k].l + t[k].r) >> 1;
        if (r <= mid)
            return queryNode(l, r, ls(k));
        if (l > mid)
            return queryNode(l, r, rs(k));
        return queryNode(l, r, ls(k)) + queryNode(l, r, rs(k));
    }

    T query(int l, int r, int k = 1)
    {
        return queryNode(l, r, k).w;
    }
};

cpp

struct lazy

template <typename T>
struct seg
{
    struct node
    {
        int l, r;
        T w;
        struct lazytag
        {
            T mul, add; // x -> x * mul + add
            lazytag(T _mul = 1, T _add = 0) : mul(_mul), add(_add) {}
            lazytag operator+(const lazytag &other) const { return lazytag(mul * other.mul, add * other.mul + other.add); }
        } lazy;

        node operator+(const node &other) const { return {l, other.r, w + other.w, lazytag()}; }
    };

    vector<T> w;
    vector<node> t;

    inline int ls(int k) { return k << 1; }
    inline int rs(int k) { return k << 1 | 1; }

    seg(int n)
    {
        w.resize(n + 1);
        t.resize((n << 2) + 1);
        build(1, n);
    }

    seg(const vector<T> &in)
    {
        int n = in.size() - 1;
        w = in;
        t.resize((n << 2) + 1);
        build(1, n);
    }

    inline void apply(int k, const typename node::lazytag &lz)
    {
        t[k].w = t[k].w * lz.mul + (t[k].r - t[k].l + 1) * lz.add;
        t[k].lazy = t[k].lazy + lz;
    }

    inline void pushup(int k)
    {
        t[k] = t[ls(k)] + t[rs(k)];
    }

    inline void pushdown(int k)
    {
        if (t[k].lazy.mul == 1 && t[k].lazy.add == 0)
            return;
        apply(ls(k), t[k].lazy);
        apply(rs(k), t[k].lazy);
        t[k].lazy = typename node::lazytag();
    }

    void build(int l, int r, int k = 1)
    {
        if (l == r)
        {
            t[k] = {l, r, w[l], typename node::lazytag()};
            return;
        }
        int mid = (l + r) >> 1;
        t[k] = {l, r, 0, typename node::lazytag()};
        build(l, mid, ls(k));
        build(mid + 1, r, rs(k));
        pushup(k);
    }

    void modify(int l, int r, const typename node::lazytag &lz, int k = 1)
    {
        if (l <= t[k].l && t[k].r <= r)
        {
            apply(k, lz);
            return;
        }
        pushdown(k);
        int mid = (t[k].l + t[k].r) >> 1;
        if (l <= mid)
            modify(l, r, lz, ls(k));
        if (r > mid)
            modify(l, r, lz, rs(k));
        pushup(k);
    }

    node queryNode(int l, int r, int k = 1)
    {
        if (l <= t[k].l && r >= t[k].r)
            return t[k];
        pushdown(k);
        int mid = (t[k].l + t[k].r) >> 1;
        if (r <= mid)
            return queryNode(l, r, ls(k));
        if (l > mid)
            return queryNode(l, r, rs(k));
        return queryNode(l, r, ls(k)) + queryNode(l, r, rs(k));
    }

    T query(int l, int r, int k = 1)
    {
        return queryNode(l, r, k).w;
    }
};

using lz = seg<int>::node::lazytag; // 套别的数据类型时需要修改

cpp

01trie

struct trie
{
    struct node
    {
        aii cnt, pts;
        node()
        {
            cnt[0] = cnt[1] = 0;
            pts[0] = pts[1] = 0;
        }
    };
    vec<node> tr;
    int cur;
    trie()
    {
        tr.resize(2);
        cur = 1;
    }

    void insert(int x)
    {
        int pt = 1;
        for (int j = 30; j >= 0; j--)
        {
            int bit = (x >> j) & 1;
            if (!tr[pt].pts[bit])
            {
                cur++;
                if (cur >= tr.size())
                    tr.resize(cur + 1);
                tr[pt].pts[bit] = cur;
            }
            tr[pt].cnt[bit]++;
            pt = tr[pt].pts[bit];
        }
    }

    int query(int x, int k)
    {
        int pt = 1, ans = 0;
        for (int j = 30; j >= 0; j--)
        {
            int bit = (x >> j) & 1;
            if (tr[pt].cnt[bit] < k)
            {
                k -= tr[pt].cnt[bit];
                bit ^= 1;
                ans |= (1 << j);
            }
            pt = tr[pt].pts[bit];
        }
        return ans;
    }
};

cpp

Algorithm Template

Algorithm Template

杂 #

头文件 #

fpow/inv/C/P #

lll #

sieve&minp #

umap hash #

zmod #

三分 #

取模类 #

random #

字符串 #

KMP #

z函数 #

Manacher #

AC自动机 #

图论 #

Tarjan #

LCA #

树上倍增 #

Tarjan #

Hierholzer #

有向图 #

无向图 #

Dijkstra #

kruskal #

HK #

网络流 #

Dinic #

mcmf #

正费用 #

负费用 #

DP #

数位dp #

单lim #

双lim #

双lim+前导零 #

数学 #

高斯消元 #

拉格朗日插值 #

矩阵快速幂 #

固定大小 #

不固定大小 #

树有关结论 #

斯特林数结论 #

第一类斯特林数 #

第二类斯特林数 #

两类斯特林数关系 #

数据结构 #

DSU #

BIT #

单点1D #

区间2D #

Seg #

lazy #

unlazified #

struct lazy #

01trie #

Thirstarfish算法竞赛

杂

头文件

fpow/inv/C/P

lll

sieve&minp

umap hash

zmod

三分

取模类

random

字符串

KMP

z函数

Manacher

AC自动机

图论

Tarjan

LCA

树上倍增

Tarjan

Hierholzer

有向图

无向图

Dijkstra

kruskal

HK

网络流

Dinic

mcmf

正费用

负费用

DP

数位dp

单lim

双lim

双lim+前导零

数学

高斯消元

拉格朗日插值

矩阵快速幂

固定大小

不固定大小

树有关结论

斯特林数结论

第一类斯特林数

第二类斯特林数

两类斯特林数关系

数据结构

DSU

BIT

单点1D

区间2D

Seg

lazy

unlazified

struct lazy

01trie