个人算法模板概览（更新中）

ACM 算法 模板
Algorithm
发布日期:   2025-05-16
更新日期:   2025-09-22
文章字数:   4.7k
阅读时长:   27 分
阅读次数:  

数论

欧拉筛

vector<int> ola(int n) {
    vector<int> prime;
    prime.reserve(n / 10); 
    vector<char> vis(n + 1);
    prime.pb(2);
    for (int i = 3; i <= n; i += 2) {
        if (!vis[i]) prime.pb(i);
        for (int j = 0; i * prime[j] <= n; ++ j) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
        }
    }
    return prime;
}

快速幂

int quick_pow(int x, int n, int mod) {
    int res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

矩阵快速幂

const int p = 1e9 + 7;
// 矩阵
struct matrix {
    ll c[101][101];
    matrix() {memset(c, 0, sizeof(c));}
} A, res; // A: 原矩阵， res: 结果矩阵
ll n, k;  // n 阶矩阵， k 阶幂

// 矩阵乘法
matrix operator*(matrix &x, matrix &y) {
    matrix t; // 临时矩阵
    for (int i = 1; i <= n; ++ i) 
        for (int j = 1; j <= n; ++ j) 
            for (int k = 1; k <= n; ++ k) 
                t.c[i][j] = (t.c[i][j] + x.c[i][k]*y.c[k][j]) % p;
    return t;
}

// 快速幂
void quickpow(ll k) {
    for (int i = 1; i <= n; ++ i) res.c[i][i] = 1; // 单位矩阵
    while(k) {
        if (k & 1) res = res * A;
        A = A * A;
        k >>= 1;
    }
}

常见优化技巧

单调队列

void solve() {
    int n, k; cin >> n >> k;
    vi v(n);
    for (auto &i: v) cin >> i;
    deque<int> dq;
    for (int i = 0; i < n; ++ i) {
        while (sz(dq) && dq.front() + k <= i) dq.pop_front();
        while (sz(dq) && v[i] > v[dq.back()]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) cout << v[dq.front()] << "\n";
    }
}

排序

归并排序

const int N = 2e5 + 5;
class MS {
private:
    int b[N];
public:
    int ans = 0; // 求逆序对
    void msort(int l,int r, vector<int> &arr){
        if(l >= r) return;
        int mid = (l + r) >> 1;
        msort(l, mid, arr);
        msort(mid + 1,r,arr);
        int i = l, j = mid + 1, k = l;
        while(i <= mid && j <= r) {
            if(arr[i] <= arr[j]) b[k++] = arr[i++];
            else { b[k++] = arr[j++]; ans += mid - i + 1; }
        }
        while(i <= mid) b[k++] = arr[i++];
        while(j <= r) b[k++] = arr[j++];
        for(int i = l; i <= r; ++i) arr[i] = b[i];
    }
};

字符串

KMP算法

vector<int> ne(1e6, 0);
// KMP (主串，模式串) 返回所有模式串在子串中出现的位置
void KMP(string S,string P){
    ll n = P.size(), m = S.size();
    for (int i = 1, j = 0; i < n; ++i) {
        while(j && P[i] != P[j])
            j = ne[j - 1];
        if (P[i] == P[j])
            j++;
        ne[i] = j;
    }
    for (int i = 0, j = 0; i < m; ++i) {
        while(j && S[i] != P[j])
            j = ne[j - 1];
        if (S[i] == P[j])
            j++;
        if(j == n){
            cout << i - n + 2 << '\n';
            j = ne[j - 1];
        }
    }
}
int main() {
    string s1,s2;
    cin >> s1 >> s2;
    KMP(s1,s2);
    for(int i=0;i<s2.size();++i) cout << ne[i] << " ";
    return 0;
}

马拉车算法

const int N = 2e7 + 5;
char a[N];
char s[N << 1];
int d[N << 1];
// scanf("%s", a + 1);
int manacher(char *a) {
    int n = strlen(a + 1), k = 0;
    s[0] = '$', s[++k] = '#';
    for(int i = 1; i <= n; ++ i) {
        s[++k] = a[i];
        s[++k] = '#';
    }
    n = k, d[1] = 1;
    for(int i = 2, l, r = 1; i <= n; ++ i) {
        if(i <= r) d[i] = min(d[r-i+l], r-i+1);
        while(s[i-d[i]] == s[i+d[i]]) d[i]++;
        if(i + d[i] - 1 > r) {
            l = i - d[i] + 1;
            r = i + d[i] - 1;
        }
    }
    return *max_element(d, d + n) - 1;
}
void solve() {  
    scanf("%s", a+1);
    cout << manacher(a);
}

动态规划

01背包

// 二维dp
void solve1() {
    int n, m; cin >> n >> m;
    vi w(m + 1, 0), v(m + 1, 0);
    vvi dp(m + 1, vi(n + 1, 0));
    for (int i = 1; i <= m; ++ i) 
        cin >> w[i] >> v[i];
    for (int i = 1; i <= m; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            if (j < w[i]) 
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
        }
    }
    cout << dp[m][n] << "\n";
}

// 一维dp
void solve2() {
    int n, m; cin >> n >> m;
    vi w(m + 1, 0), v(m + 1, 0);
    vi dp(n + 1, 0);
    for (int i = 1; i <= m; ++ i) 
        cin >> w[i] >> v[i];
    for (int i = 1; i <= m; ++ i) {
        for (int j = n; j >= 1; -- j) {
            if (j >= w[i]) {
                dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
            }
        }
    }
    cout << dp[n] << "\n";    
}

多重背包

// 二进制优化
void solve() {
    vi vv, ww;  // 存体积， 存价值
    int n, m; cin >> n >> m; // 种数， 总体积
    int v, w, s; //体积， 价值， 数量
    for (int i = 1; i <= n; ++ i) {
        cin >> v >> w >> s;
        for (int j = 1; j <= s; j <<= 1) {
            vv.pb(j * v);
            ww.pb(j * w);
            s -= j;
        }
        if (s) {
            vv.pb(s * v);
            ww.pb(s * w);
        }
    }    
    // 01背包
    vi dp(m + 1);
    for (int i = 0; i < sz(vv); ++ i) {
        for (int j = m; j >= vv[i]; -- j) {
            dp[j] = max(dp[j], dp[j-vv[i]] + ww[i]);
        }
    }
    cout << dp[m];
}

二维费用背包

void solve() {
    int n, H, S;
    cin >> n >> H >> S;
    int h, s, w;
    vvi dp(H + 5, vi(S + 5));
    for (int i = 1; i <= n; ++ i) {
        cin >> h >> s >> w;
        for (int j = H; j >= h; -- j) {
            for (int k = S; k >= s; -- k) {
                dp[j][k] = max(dp[j][k], dp[j-h][k-s] + w); }
        }
    }
    cout << dp[H][S] << "\n";
}

分组背包

void solve() {
    int n, V; cin >> n >> V;
    vi v(int(2e5)), w(int(2e5));
    int s;
    vi dp(V + 1);
    for (int i = 1; i <= n; ++ i) {
        cin >> s;
        for (int j = 1; j <= s; -- j) {
            cin >> v[j] >> w[j];
        }
        for (int j = V; j >= 1; --j) {
            for (int k = 0; k <= s; ++ k) {
                if (j >= v[k]) {
                    dp[j] = max(dp[j], dp[j - v[k]] + w[k]);
                }
            }
        }
    }
    cout << dp[V] << "\n";
}

混合背包

void solve() {
    int n, m; cin >> n >> m;
    vi a, b, c;
    int v, w, s;
    for (int i = 1; i <= n; ++ i) {
        cin >> v >> w >> s;
        if (s == 0) {
            a.pb(v);b.pb(w);c.pb(0);
        } else {
            if (s == -1) s = 1;
            int k = 1;
            while (s >= k) {
                a.pb(k * w);b.pb(k * w);c.pb(1);
                s -= k;k <<= 1;
            } if(s) {
                a.pb(s * v);b.pb(s * w);c.pb(1);
            }
        }
    }
    vi dp(m);
    for (int i = 1; i < sz(c); ++ i) {
        if (c[i] == 1) 
            for (int j = m; j >= a[i]; -- j) 
                dp[j] = max(dp[j], dp[j-a[i]] + b[i]);
        else 
            for (int j = a[i]; j <= m; ++ j)
                dp[j] = max(dp[j], dp[j-a[i]] + b[i]);
    }
    cout << dp[m] << "\n";
}

完全背包

void solve() {// 二维dp
    int n, m; cin >> n >> m; // 采药时间和草药种数    
    vi t(m + 1), v(m + 1); // 每株草药的采集时间和价值
    vvi dp(m + 1, vi(n + 1)); // dp数组
    for(int i = 1; i <= m; ++ i) {
        cin >> t[i] >> v[i];
    }
    for (int i = 1; i <= m; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-t[i]] + v[i]);
        }
    }
    cout << dp[m][n];
}
void solve2() {// 一维dp
    int n, m;
    cin >> n >> m;
    vi t(m + 1), v(m + 1);
    for (int i = 1; i <= m; ++ i) {
        cin >> t[i] >> v[i];
    }
    vi dp(n + 1);
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++ j) {
            if(j >= t[i])
                dp[j] = max(dp[j], dp[j-t[i]] + v[i]);
        }
    }
    cout << dp[n];
}

数据结构

并查集

struct DSU {
    int par[N],rk[N];
    // 初始化n个元素
    void init(int n) {
        for(int i = 1;i <= n;++i) par[i] = i, rk[i] = 0;
    }
    // 查询树的根 (路径压缩)
    int find(int x) {
        return par[x] = par[x] == x ? x : find(par[x]);
    }
    // 普通合并
    int unite(int x, int y) {
        x = find(x);y = find(y);
        return x == y ? 0 : par[x] = y;
    }
    // 按秩合并
    void merge(int x, int y) {
        x = find(x);y = find(y);
        if(x == y) return;
        if(rk[x] > rk[y]) swap(x, y);
        par[x] = y;
        if(rk[x] == rk[y]) rk[y]++;
    }
    // 判断x和y是否联通
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

树的直径

const int N = 1e5 + 5;
vector<int> e[N];
int ans = 0, poi = 0;
int vis[N];
void dfs(int x, int dep) {
    vis[x] = 1;
    for(auto v : e[x]) {
        if(!vis[v]) dfs(v, dep+1);
    }
    if(dep > ans) {
        ans = dep;
        poi = x;
    }
}
void solve() {
    int n; cin >> n;
    int a, b;
    for(int i=0;i<n-1;++i) {
        cin >> a >> b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dfs(1, 1);
    memset(vis, 0, sizeof(vis));
    dfs(poi, 1);
    cout << ans-1;
}

树链剖分-最近公共祖先

const int N = 5e5 + 5; 
vector<int> G[N];
int fa[N], dep[N], son[N], sz[N];
int top[N];
void dfs1(int u, int father) {
    fa[u] = father,dep[u] = dep[father] + 1,sz[u] = 1;
    for(auto v : G[u]) {
        if(v == father) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[son[u]] < sz[v]) son[u] = v;
    }
}
void dfs2(int u, int t) {
    top[u] = t;
    if(!son[u]) return;
    dfs2(son[u], t);
    for(auto v : G[u]) {
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}   
int lca(int u, int v) {
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}
void solve(){
    int n, m, s; cin >> n >> m >> s;
    for(int i=0;i<n-1;++i) {
        int a, b; cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    dfs1(s, 0);
    dfs2(s ,s);
    for(int i=0;i<m;++i) {
        int u, v; cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
}

树状数组

int n,m;
int a[MAXN],c[MAXN];
int lowbit(int x) {
    return x & (-x);
}
int sum(int x) {
    int res = 0;
    for(int i = x; i ; i -= lowbit(i)) res += c[i];
    return res;
}
void add(int x,int y) {
    for(int i = x; i <= n; i += lowbit(i)) c[i] += y;
}

线段树

int n, w[N];
// 树的结点 
struct node {
    int l, r, sum, add; 
}tr[N*4];
// 向上更新
void pushup(int p) {
    tr[p].sum = tr[lc].sum + tr[rc].sum;
}
// 向下更新
void pushdown(int p) {
    if(tr[p].add) {
        tr[lc].sum += (tr[lc].r - tr[lc].l + 1) * tr[p].add;
        tr[rc].sum += (tr[rc].r - tr[rc].l + 1) * tr[p].add;
        tr[lc].add += tr[p].add;
        tr[rc].add += tr[p].add;
        tr[p].add = 0;
    }
}
// 建树 build(根结点,左子树,右子树)
void build(int p, int l, int r) {
    tr[p] = {l, r, w[l], 0};
    if(l == r) return;
    int m = (l + r) >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(p);
}
// 区间修改 
void update(int p, int x, int y, int k) {
    if(x <= tr[p].l && tr[p].r <= y) {
        tr[p].sum += (tr[p].r - tr[p].l + 1) * k;
        tr[p].add += k;
        return;
    }
    int m = (tr[p].l + tr[p].r) >> 1;
    pushdown(p);
    if(x <= m) update(lc, x, y, k);
    if(y > m) update(rc, x, y, k);
    pushup(p);
}
// 区间查询
int query(int p, int x, int y) {
    if(x <= tr[p].l && tr[p].r <= y) return tr[p].sum;
    int m = (tr[p].l + tr[p].r) >> 1;
    pushdown(p);
    int sum = 0;
    if(x <= m) sum += query(lc, x, y);
    if(y > m) sum += query(rc, x, y);
    return sum;
}
// 单点修改
void update(int p, int x, int k) {
    if(tr[p].l == x && tr[p].r == x) {
        tr[p].sum = k;
        return;
    }
    int m = (tr[p].l + tr[p].r) >> 1;
    if(x <= m) update(lc, x, k);
    if(x > m)  update(rc, x, k);
    tr[p].sum = tr[lc].sum + tr[rc].sum;
}
// 单点查询
int get(int x) {
    return query(1, x, x);  // 查询区间 [x, x] 的值
}

字典树

#define MAXN 2000 * 75 + 5
int trie[MAXN][26]; //每个结点都有可能有26个子结点
int word[MAXN]; //用于记录以这个结点为单词末尾单词个数
char str[80];
// n个字符串,最长链长为ans
int n, tot = 0,ans = 0;
// 字典树,插入字符串,最长链长为ans
void insert (char *str) {
    int u = 0; //根结点
    int len = strlen(str);
    int res = 0; //表示字典树路径上存有几个别的单词
    for (int i = 0; i < len;++i) {
        int a = str[i] - 'a'; //映射小写字母
        if (trie[u][a] == 0) //如果没有这个结点
            trie[u][a] = ++tot;
        u = trie[u][a]; //跳转到该结点
        res += word[u]; //如果这个结点存有单词则增加
    }
    word[u]++; //以该结点结尾的单词的个数加一
    if (res + 1 > ans) //比较链长最大值
        ans = res + 1;
}

ST表

inline int gcd(int a,int b) {
    return b == 0 ? a : gcd(b, a % b);
}
inline int lcm(int a,int b) {
    return (a / gcd(a, b)) * b % mod;
}
const int MAXN = 2e5 + 5;  // 假设数组的最大长度
const int LOG = 18;    // 对应 log2(MAXN) + 1
//int min_arr[MAXN][LOG];      // 最小值
//int max_arr[MAXN][LOG];      // 最大值
//int gcd_arr[MAXN][LOG];      // GCD
int lcm_arr[MAXN][LOG];      // LCM
int log_2[MAXN + 1]; // 预计算 log2

// 预处理：构建 ST 表
void buildST(vector<int>& arr) {
    int n = arr.size();
    // 初始化 log2Table
    log_2[1] = 0;
    for (int i = 2; i <= n; ++i) {
        log_2[i] = log_2[i / 2] + 1;
    }
    // 初始化 ST 表的第一列
    for (int i = 1; i <= n; ++i) {
        //max_arr[i][0] = arr[i];
        //min_arr[i][0] = arr[i];
        //gcd_arr[i][0] = arr[i];
        lcm_arr[i][0] = arr[i];
    }
    // 填充 ST 表
    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            //max_arr[i][j] = max(max_arr[i][j - 1], max_arr[i + (1 << (j - 1))][j - 1]);
            //min_arr[i][j] = min(min_arr[i][j - 1], min_arr[i + (1 << (j - 1))][j - 1]);
            //gcd_arr[i][j] = gcd(gcd_arr[i][j - 1], gcd_arr[i + (1 << (j - 1))][j - 1]);
            lcm_arr[i][j] = lcm(lcm_arr[i][j - 1], lcm_arr[i + (1 << (j - 1))][j - 1]) % mod;
        }
    }
}

// 查询区间 [L, R] 的最大值
// int query_max(int L, int R) {
//     int len = R - L + 1;
//     int j = log_2[len];
//     return max(max_arr[L][j], max_arr[R - (1 << j) + 1][j]);
// }
// // 查询区间 [L, R] 的最小值
// int query_min(int L, int R) {
//     int len = R - L + 1;
//     int j = log_2[len];
//     return min(min_arr[L][j], min_arr[R - (1 << j) + 1][j]);
// }
// // 查询区间 [L, R] 的gcd
// int query_gcd(int L, int R) {
//     int len = R - L + 1;
//     int j = log_2[len];
//     return gcd(gcd_arr[L][j], gcd_arr[R - (1 << j) + 1][j]);
// }
// 查询区间 [L, R] 的lcm
int query_lcm(int L, int R) {
    int len = R - L + 1;
    int j = log_2[len]; 
    return lcm(lcm_arr[L][j], lcm_arr[R - (1 << j) + 1][j]);
}

图论

dijkstra最短路

struct Dijkstra {
    struct Edge { int v, w; };
    int n;
    vector<vector<Edge>> G;
    vector<int> d, vis, path, cnt;
    Dijkstra(int _n): n(_n) {
        G.assign(n + 1, {});
        d.assign(n + 1, inf);
        vis.assign(n + 1, 0);
        path.assign(n + 1, -1);
        cnt.assign(n + 1, 0);
    }
    void add(int u, int v, int w) {
        G[u].push_back({v, w});
    }
    void dijkstra(int s) {
        d[s] = 0;
        cnt[s] = 1;
        // 小顶堆，存 {dist, u}
        using pii = pair<int, int>;
        priority_queue<pii, vector<pii>, greater<>> pq;
        pq.push({0, s});
        
        while (!pq.empty()) {
            auto [_u, u] = pq.top(); pq.pop();
            if (vis[u]) continue;
            vis[u] = 1;

            for (auto &e : G[u]) {
                int v = e.v, w = e.w;
                if (d[v] > d[u] + w) {
                    d[v] = d[u] + w;
                    path[v] = u;
                    cnt[v] = cnt[u];
                    pq.push({d[v], v});
                } else if (d[v] == d[u] + w) {
                    cnt[v] += cnt[u];
                }
            }
        }
    }

    // 获取从 s 到 u 的路径，若无路径返回空向量
    vector<int> getPath(int u, int s) {
        vector<int> res;
        if (d[u] == inf) return res;
        for (int cur = u; cur != -1; cur = path[cur]) {
            res.push_back(cur);
            if (cur == s) break;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

拓扑排序

const int N = 105;
// G[] 存图, tp[] 拓扑排序的结果
vector<int> G[N], tp; 
int din[N]; // 入度 (存图时记得计算入度)
int n; // 点数
bool toposort() {
    queue<int> q;
    for(int i=1;i<=n;++i) {
        if(din[i]==0) q.push(i);
    } 
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        tp.push_back(x);
        for(auto c : G[x]) {
            if(--din[c] == 0) q.push(c);
        }
    }
    return tp.size() == n;
}

二分图判定-染色法

// 二分图判定-染色法
const int M = 1005, N = 1e5;
struct edge {
    int v, w, ne; // 终点,边权,下一条边
}e[M]; // 边集
int idx, h[N], color[N];
// 记得加 memset(h, -1, sizeof(h)); 
// 带权添加
void add(int a, int b, int w) {
    e[idx] = {b, w, h[a]};
    h[a] = idx++;
}
// 染色法二分图的判定
bool dfs(int u, int c) {
    color[u] = c;
    for(int i=h[u];i;i=e[i].ne) {
        int v = e[i].v;
        if(!color[v]) {
            if(dfs(v, 3-c)) return 1;
        }
        else if(color[v] == c) return 1;
    }
    return 0;
}
bool flag = 0;
bool check(int n) {
    for(int i=1;i<=n;++i) {
        if(!color[i]) {
            if(dfs(i,1)) {
                flag = 1;
                break;
            }
        }
    }
    if(flag) return 0;
    else return 1;
}

二分图最大匹配-匈牙利算法

// 二分图最大匹配-匈牙利算法
int n, m, k, ans;
const int M = 1005, N = 1e5 + 5;
struct edge {
    int v, ne; // 终点,边权,下一条边
}e[N]; // 边集
int idx, h[N];
int vis[N], match[N];
// 记得加 memset(h, -1, sizeof(h)); 
// 带权添加
void add(int a, int b) {
    e[++idx] = {b, h[a]};
    h[a] = idx;
}
bool dfs(int u) {
    for(int i=h[u];i;i=e[i].ne) {
        int v = e[i].v;
        if(vis[v]) continue;
        vis[v] = 1;
        if(!match[v] || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

强连通分量

const int N = 1e5 + 5 ;
vector<int> e[N];
// 时间戳 dfn[x], 追溯值low[x] 
int dfn[N], low[N], tot; 
// 手写栈
int stk[N], instk[N], top;
// SCC数组, SCC大小
int scc[N], siz[N], cnt;
void tarjan(int x) {
    dfn[x] = low[x] = ++tot;
    stk[++top] = x, instk[x] = 1;
    for(int y : e[x]) {
        if(!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if(instk[y]) 
            low[x] = min(low[x], dfn[y]);
    }
    if(dfn[x] == low[x]) {
        int y; ++cnt;
        do {
            y = stk[top--]; instk[y] = 0;
            scc[y] = cnt;
            ++siz[cnt];
        }while(y != x);
    }
}

最小生成树

// 并查集
class DSU {
private:
    int par[N],rk[N];
public:
    // 初始化n个元素
    void init(int n) {
        for(int i = 1;i <= n;++i) par[i] = i, rk[i] = 0;
    }
    // 查询树的根 (路径压缩)
    int find(int x) {
        return par[x] = par[x] == x ? x : find(par[x]);
    }
    // 普通合并
    int unite(int x, int y) {
        x = find(x);y = find(y);
        return x == y ? 0 : par[x] = y;
    }
    // 按秩合并
    void merge(int x, int y) {
        x = find(x);y = find(y);
        if(x == y) return;
        if(rk[x] > rk[y]) swap(x, y);
        par[x] = y;
        if(rk[x] == rk[y]) rk[y]++;
    }
    // 判断x和y是否联通
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};
// 最小生成树 kruskal算法
class MST : DSU {
private:
    struct edge{
        int u, v, cost;
        bool operator<(const edge& other) const {
            return cost < other.cost; // 按权值升序排序
        }
    };
    vector<edge> es; // 边集
    vector<edge> mst; //最小生成树边集
    int V, res; //V:点数 res:MST各边长之和
public:
    MST(int n) : V(n) {} // 构造函数, 赋值V为n
    int kruskal() {
        sort(es.begin(), es.end());
        init(V);
        mst.clear();
        res =  0;
        for(auto &e : es) {
            if(!same(e.u, e.v)) {
                unite(e.u, e.v);
                mst.push_back(e);
                res += e.cost;
            }
        }
        return res;
    }
    // 加边, 权
    void addedge(int u, int v, int cost) {
        es.push_back({u, v, cost});
    }
    // 判断是否连通, 先要使用kruskal算法
    bool isConnected() {
        set<int> st;
        for (int i = 1; i <= V; ++i) {
            st.insert(find(i));
        }
        return st.size() == 1;
    }
};

FHQ Treap

struct node {
    int l, r;
    int val;
    int key;
    int sz;
}tree[N];
int n, root, idx;
int newnode(int v) {
    tree[++idx].val = v;
    tree[idx].key = rand();
    tree[idx].sz = 1;
    return idx;
}
void pushup(int p) {
    tree[p].sz = tree[tree[p].l].sz
        + tree[tree[p].r].sz + 1;
}
void split(int p, int v, int &x, int &y) {
    if(!p) {
        x = y = 0;
        return;
    }
    if(tree[p].val <= v) {
        x = p;
        split(tree[x].r, v, tree[x].r, y);
    } else {
        y = p;
        split(tree[y].l, v, x, tree[y].l);
    }
    pushup(p);
}
int merge(int x, int y) {
    if(!x || !y) return x + y;
    if(tree[x].key < tree[y].key) {
        tree[x].r = merge(tree[x].r, y);
        pushup(x);
        return x;
    } else {
        tree[y].l = merge(x, tree[y].l);
        pushup(y);
        return y;
    }
}
void insert(int v) {
    int x, y, z;
    split(root, v, x, y);
    z = newnode(v);
    root = merge(merge(x, z), y);
}
void del(int v) {
    int x, y, z;
    split(root, v, x, z);
    split(x, v-1, x, y);
    y = merge(tree[y].l, tree[y].r);
    root = merge(merge(x, y), z);
}
int get_k(int p, int k) {
    if(k <= tree[tree[p].l].sz) 
        return get_k(tree[p].l, k);
    if(k == tree[tree[p].l].sz + 1) 
        return p;
    return get_k(tree[p].r, k-tree[tree[p].l].sz-1);
}

Tarjan算法-最近公共祖先

const int N = 5e5 + 5;
vector<int> G[N];
vector<pair<int,int>> q[N];
int fa[N], vis[N], ans[N];
int find(int x) {
    return fa[x] = fa[x] == x ? x : find(fa[x]);
}
void tarjan(int u) {
    vis[u] = true;
    for(auto v : G[u]) {
        if(!vis[v]) {
            tarjan(v);
            fa[v] = u;
        }
    }
    for(auto qu : q[u]) {
        int v = qu.first, i = qu.second;
        if(vis[v]) ans[i] = find(v);
    }
}
文章作者: Cysheper
文章链接: https://cysheper.github.io/2025/05/16/suan-fa-mo-ban-gai-lan/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Cysheper !
ACM 算法 模板
评论
  目录