蒟蒻的模板

RainbowAutomaton / 2024-02-07 / 原文

蒟蒻 Rainbow_Automaton 的模板

$\text{2023-10}$ 备战 $\text{csp-s}$

只是目前会的

~~然而目前啥也不会...~~

代码注意事项

不要使用using namespace std;
min 和 max 都可以直接 std::min std::max 吧
关同步 #define fastread std::ios_sync_with_stdio (false); cin.tie (0);
学习 jiangly using i64 = long long

图论

存图

~~这种东西真的需要记吗~~

写一个神秘的封装好的图

template<int maxn, int maxm>
struct Graph {
    struct Edge {
        int u, v;
        int pre;
    } es[maxm << 1];

    int last[maxn], cnt;

    Graph () { cnt = 0; memset (last, 0, sizeof (last)); }

    inline void addEdge (int u, int v) {
        es[++cnt] = Edge { u, v, last[u] };
        last[u] = cnt;
    }
};

然而我大部分时侯都不会用到封装好的图...

一般情况下只会直接写 Graph 里面的东西

最短路

Dijkstra

struct Node {
    int id;
    int dis;

    friend bool operator < (Node a, Node b) {
        return a.dis > b.dis; // 通过改符号的方向实现小根堆...
    }
};

std::priority_queue<Node> q;

int dis[maxn];
bool vis[maxn];
inline void dij (int S) {
    memset (vis, 0, sizeof (vis));
    memset (dis, 0x3f, sizeof (dis)); dis[S] = 0;
    q.push (Node { S, dis[S] });

    while (not q.empty()) {
        int now = q.top ().id; q.pop ();

        if (vis[now]) { continue; }
        vis[now] = true;

        for (int i = last[now]; i; i = es[i].pre) {
            int t = es[i].v;

            if (dis[t] > dis[now] + es[i].w) {
                dis[t] = dis[now] + es[i].w;
                q.push (Node { t, dis[t] });
            }
        }
    }
}

某个广为人所知的最短路算法

判负环

不判负环最好别用

~~才发现我单源最短路都是用 Dijkstra 过的~~

~~甚至找不到一个SPFA的板子~~

std::queue<int> q;
bool inq[maxn];
int times[maxn];

int dis[maxn];
inline bool spfa (int S) {
    q.push (S);
    memset (inq, 0, sizeof (inq)); inq[S] = true;
    memset (times, 0, sizeof (times)); times[S] = 0;
    for (int i = 1; i <= n + 1; i++) { if (i != S) { dis[i] = inf; } }

    while (not q.empty ()) {
        int now = q.front (); q.pop ();
        inq[now] = false;

        for (int i = last[now]; i; i = es[i].pre) {
            int t = es[i].v;

            if (dis[t] > dis[now] + es[i].w) {
                dis[t] = dis[now] + es[i].w;

                if (not inq[t]) {
                    inq[t] = true;
                    times[t] ++; if (times[t] > n + 1) { return false; } // 此处n + 1是因为多了一个超级源

                    q.push (t);
                }
            }
        }
    }

    return true;
}

差分约束

~~也许是唯一能用上SPFA的地方吧...~~

可以解出 $m$ 个形如 $X_u - X_v \leq Y$ 的不等式组成的不等式组的一个解

~~自然也可以判断是否有解~~

实质就是 $u - v \leq w \implies u \leq v + w \implies Edge_{v, u, w} $

$v$ 到 $u$ 连一条长度为 $w$ 的边

inline void diff_constraints () { // 差分约束
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;

        addEdge (v, u, w);
    }

    // 以n + 1作为超级源点
    for (int i = 1; i <= n; i++) { addEdge (n + 1, i, 0); }

    if (not spfa (n + 1)) { cout << "NO" << endl; }
    else {
        for (int i = 1; i <= n; i++) { cout << dis[i] << " "; }
    }
}

Floyd

int dis[maxn][maxn];

inline void init () {
    memset (dis, 0x3f, sizeof (dis));
    for (int i = 1; i <= n; i++) { dis[i][i] = 0; }
}

inline void floyd () {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dis[i][j] = std::min (dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

注意先 init() 再加边

倍增Floyd

实际上是矩阵快速幂

把 $\text{Floyd}$ 原来的用 $dp[k][i][j]$ 表示前 $k$ 个点中 $i$ 到 $j$ 的最短路

改为用 $dp[s][i][j]$ 表示长度为 $s$ 的 $i$ 到 $j$ 的最短路

显然

$dp[s][i][j]$ 可以由 $ \min\limits_{k = 1}^{n} {dp[s - 1][i][k] + dp[1][k][j]}$ 转移过来

然后我们发现转移的过程和矩阵乘法特别像

用快速幂求出 $dp^k$ 就可以得到长为 $k$ 的路径条数

传递闭包

实际上就是 $01$ 矩阵上的 $\text{Floyd}$

只是求最短路改成求连通性了

std::bitset<maxn> a[maxn];

inline void floydClosure () {
    for (int j = 1; j <= n; j++) {
        for (int i = 1; i <= n; i++) {
            if (a[i][j]) { // i 能到 j
                a[i] |= a[j]; // 用j更新i
            }
        }
    }
}

上面的代码是用 bitset 写的, 与传统 $\text{Floyd}$ 略有不同

但是其基本思想是类似的

生成树

Kruskal

struct Edge {
    int u, v, w;

    friend bool operator < (Edge a, Edge b) {
        return a.w < b.w;
    }
};
std::vector<Edge> es;

inline int kruskal () {
    std::sort (es.begin (), es.end ());
    init ();

    int ans = 0;
    int tot = 0;

    for (auto e : es) {
        int u = find (e.u);
        int v = find (e.v);

        if (u == v) { continue; }

        fa[u] = v;
        ans += e.w;

        tot ++;
        if (tot == n - 1) { return ans; }
    }

    return -1;
}

其中 init() 就是并查集的 init()

并查集的写法看数据结构部分吧

Tarjan 系列

强连通分量

int low[maxn], dfn[maxn], dpos;
int stk[maxn], spos;
bool ins[maxn];

int belong[maxn], scc_cnt;
std::set<int> scc[maxn];

void tarjan (int now) {
    low[now] = dfn[now] = ++dpos;
    stk[++spos] = now;
    ins[now] = true;

    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t);
            low[now] = std::min (low[now], low[t]);
        } else if (ins[t]) {
            low[now] = std::min (low[now], dfn[t]);
        }
    }

    if (low[now] == dfn[now]) {
        scc_cnt ++;
        do {
            belong[now] = scc_cnt;
            scc[scc_cnt].insert (now);
            ins[now] = false;

            now = stk[spos--];
        } while (low[now] != dfn[now]);
    }
}

2-SAT

用 $1$ 到 $n$ 表示 $a_i$ 取 $0$

用 $n + 1$ 到 $2 \times n$ 表示 $a_{i - n}$ 取 $1$

for (int i = 1; i <= 2 * n; i++) {
    if (not dfn[i]) { tarjan (i); }
}

if (not check ()) { std::cout << "IMPOSSIBLE" << "\n"; return 0; }

std::cout << "POSSIBLE" << "\n";
for (int i = 1; i <= n; i++) {
    if (scc[i + n] < scc[i]) { std::cout << 1 << " "; }
    else { std::cout << 0 << " "; }
}

割点

int low[maxn], dfn[maxn], dpos;
bool cut[maxn];

void tarjan (int now, int fa) {
    low[now] = dfn[now] = ++dpos;

    int sons = 0;
    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t, now);
            low[now] = std::min (low[now], low[t]);
            sons ++;
            if (low[t] >= dfn[now]) { cut[now] = true; }
        } else { // 此处可以考虑父亲
            low[now] = std::min (low[now], dfn[t]);
        }            
    }

    if (fa == 0 and sons < 2) { cut[now] = false; } 
}

点双连通分量

int low[maxn], dfn[maxn], dpos;
int stk[maxn], spos;

int belong[maxn], vdcc_cnt;
std::vector<int> vdcc[maxn];

void tarjan (int now, int fa) {
    low[now] = dfn[now] = ++dpos;
    stk[++spos] = now;

    int sons = 0;
    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t, now);
            low[now] = std::min (low[now], low[t]);

            sons ++;

            if (low[t] >= dfn[now]) {
                ++vdcc_cnt;

                int last = 0;
                while (last != t) {
                    int top = stk[spos--];
                    belong[top] = vdcc_cnt;
                    vdcc[vdcc_cnt].push_back (top);         
                    last = top;
                }
                vdcc[vdcc_cnt].push_back (now);
            }    
        } else {
            low[now] = std::min (low[now], dfn[t]);
        }
    }

    if (fa == 0 and sons == 0) { vdcc_cnt ++; vdcc[vdcc_cnt].push_back (now); }
}

桥

int low[maxn], dfn[maxn], dpos;
bool bridge[maxm << 1];

void tarjan (int now, int in_edge) {
    low[now] = dfn[now] = ++dpos;

    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t, i);
            low[now] = std::min (low[now], low[t]);

            if (low[t] > dfn[now]) { bridge[i] = bridge[i ^ 1] = true; }

        } else if (i != (in_edge ^ 1)) {
            low[now] = std::min (low[now], dfn[t]);
        }
    }
}

inline void init () { cnt = 1; }

因为涉及到快速找反向边, 一定要把 cnt 初始化为1!

边双连通分量

int low[maxn], dfn[maxn], dpos;
bool bridge[maxm << 1];

void tarjan (int now, int in_edge) {
    low[now] = dfn[now] = ++dpos;

    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not dfn[t]) {
            tarjan (t, i);
            low[now] = std::min (low[now], low[t]);

            if (low[t] > dfn[now]) { bridge[i] = bridge[i ^ 1] = true; }

        } else if (i != (in_edge ^ 1)) {
            low[now] = std::min (low[now], dfn[t]);
        }
    }
}   

int belong[maxn], edcc_cnt;
std::vector<int> edcc[maxn];

void dfs (int now) {
    belong[now] = edcc_cnt;
    edcc[edcc_cnt].push_back (now);
    for (int i = last[now]; i; i = es[i].pre) {
        int t = es[i].v;
        if (bridge[i]) { continue; }
        if (belong[t]) { continue; }

        dfs (t);
    }
}

inline void init () { cnt = 1; }

网络流

网络流的加边方式与普通图论问题的加边方式略有不同

struct Edge {
   int u, v;
   int pre;
   long long flow;
} es[maxm << 1];

int last[maxn], cur[maxn], cnt = 1;
int S, T;

inline void _addEdge (int u, int v, long long cap) {
   es[++cnt] = Edge { u, v, last[u], cap };
   last[u] = cnt;
}

inline void addEdge (int u, int v, long long cap) {
   _addEdge (u, v, cap);
   _addEdge (v, u, 0);
}

Dinic

int dep[maxn];

bool bfs () {
    std::queue<int> q; q.push (S);
    memset (dep, 0x3f, sizeof (dep)); dep[S] = 1;

    while (not q.empty ()) {
        int now = q.front (); q.pop ();

        for (int i = last[now]; i; i = es[i].pre) {
            int t = es[i].v;
            if (not es[i].flow) { continue; }
            if (dep[t] != 0x3f3f3f3f) { continue; }

            dep[t] = dep[now] + 1;
            q.push (t);
        }
    }

    return dep[T] != 0x3f3f3f3f;
}

long long dfs (int now, long long now_flow) {
    if (now == T or not now_flow) { return now_flow; }

    long long res = 0;
    for (int &i = cur[now]; i; i = es[i].pre) {
        int t = es[i].v;

        if (not es[i].flow) { continue; }
        if (dep[t] != dep[now] + 1) { continue; }

        long long t_flow = dfs (t, std::min (now_flow, es[i].flow));

        if (t_flow) {
            es[i].flow -= t_flow;
            es[i ^ 1].flow += t_flow;
            now_flow -= t_flow;
            res += t_flow;

            if (not now_flow) { return res; }
        }
    }

    return res;
}

inline long long Dinic (int _s, int _t) {
    S = _s, T = _t;
    long long res = 0;
    while (bfs ()) {
        memcpy (cur, last, sizeof (last));
        res += dfs (S, 0x3f3f3f3f);
    }
    return res;
}

网络单纯形

咕咕咕

呜呜呜本来是会的

字符串

啥也不会

后缀自动机

struct SAM {
    struct Node {
        int ch[26];
        int fa;
        int len;
    } ns[maxn];

    int last, root, tot;

    // 附加信息
    i64 cnt[maxn];

    SAM () { last = root = tot = 1; memset (cnt, 0, sizeof (cnt)); }

    inline void add (int c) {
        int p = last;
        int np = last = ++tot;

        ns[np].len = ns[p].len + 1;
        cnt[np] = 1;

        for (; p and not ns[p].ch[c]; p = ns[p].fa) { ns[p].ch[c] = np; }

        if (not p) { ns[np].fa = root; }
        else {
            int q = ns[p].ch[c];

            if (ns[q].len == ns[p].len + 1) { ns[np].fa = q; }
            else {
                int nq = ++tot;
                ns[nq] = ns[q]; ns[nq].len = ns[p].len + 1;
                ns[q].fa = ns[np].fa = nq;

                for (; p and ns[p].ch[c] == q; p = ns[p].fa) { ns[p].ch[c] = nq; }
            }
        }
    }    

    inline void getParentTree (Graph& tr) {
        for (int i = 2; i <= tot; i++) { tr.addEdge (ns[i].fa, i); }
    }
};

数学

快速幂

i64 ksm (i64 a, i64 b, i64 mod) {
    i64 res = 1;
    i64 base = a;

    while (b) {
        if (b & 1) { (res *= base) %= mod; }
        (base *= base) %= mod;
        b >>= 1;
    }    

    return res;
}

欧拉函数

i64 phi (i64 n) {
    i64 ans = n;
    for (i64 p = 2; p * p <= n; p++) {
        if (n % p != 0) { continue; }

        ans = ans / p * (p - 1);
        while (n % p == 0) { n /= p; }
    }

    if (n > 1) { ans = ans / n * (n - 1); }

    return ans;
}

逆元

这里使用欧拉函数求逆元

~~不会写exgcd导致的~~

你说的对, 但是 $a ^ {\varphi(b)} = 1 \pmod b$

所以我们可以直接求逆元

i64 inv (i64 a, i64 b) {
    return Ksm::ksm (a, phi (b) - 1, b);
}

exgcd

i64 exgcd (i64 a, i64 b, i64 &x, i64 &y) {
    if (b == 0) { x = 1, y = 0; return a; }
    i64 d = exgcd (b, a % b, y, x);
    y -= x * (a / b);
    return d;
}

于是, 上面的逆元也可以用exgcd求

因为

\[a \times inv_a \equiv 1 \pmod b \\ a \times inv_a + b \times y = 0 \]

所以我们很容易用exgcd求出 $inv_a$

inline i64 inv (i64 a, i64 b) {
    i64 x, y; exgcd (a, b, x, y);
    return (x + b) % b;       
}

线性筛

std::bitset<maxn> not_prime;
std::vector<int> primes;

inline void get_primes () {
    not_prime.reset ();
    not_prime[1] = true;

    for (int i = 2; i <= n; i++) {
        if (not not_prime[i]) { primes.push_back (i); }

        for (auto p : primes) {
            if (i * p > n) { break; }
            not_prime[i * p] = true;
            if (i % p == 0) { break; }
        }
    }
}

线性筛莫比乌斯函数

顺便求出前缀和

inline void get_mu () {
    not_prime.reset ();
    int n = maxn - 5;

    mu[1] = 1;
    not_prime[1] = true;

    for (int i = 2; i <= n; i++) {
        if (not not_prime[i]) { primes.push_back (i); mu[i] = -1; }

        for (auto p : primes) {
            if (i * p > n) { break; }
            not_prime[i * p] = true;
            mu[i * p] = -1 * mu[i];

            if (i % p == 0) { mu[i * p] = 0; break; }
        }
    }

    for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + mu[i]; }
}

中国剩余定理

只会大数翻倍法

~~orz钟神太强了%%%~~

inline bool merge (i64 &m1, i64 &a1, i64 m2, i64 a2) {
    if (m1 < m2) { std::swap (m1, m2); std::swap (a1, a2); }           

    while (a1 % m2 != a2) { a1 += m1; }

    m1 = lcm (m1, m2);

    return true;
}

扩展中国剩余定理

不用害怕, zhx的大数翻倍法本身就能合并两个同余方程

所以合并部分代码跟上面一样

数据结构

并查集

template <int maxn>
struct UnionFindSet {
    int fa[maxn];  
    
    inline void init () {
        for (int i = 1; i <= n; i++) { fa[i] = i; }
    }

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

    inline void merge (int x, int y) {
        fa[find (y)] = find (x);
    }
    
    inline bool same (int x, int y) {
        return find (x) == find(y);
    }
};

树状数组

template <int maxsiz>
struct BIT {
    int tr[maxsiz];

    inline int lowbit (int x) { return x & (-x); }

    inline void add (int pos, int val) { for (int i = pos; i <= n; i += lowbit(i)) { tr[i] += val; } }
    inline int _query (int pos) { int res = 0;for (int i = pos; i; i -= lowbit(i)) { res += tr[i]; } return res; }

    inline int query (int l, int r) { return _query (r) - _query (l - 1); }
};

上面只给出了单点加区间求和的版本

实际上, 树状数组还可以通过神秘的技术实现区间加单点查和 区间加区间求和

甚至可以通过跳 lowbit 实现 区间最值查询

然而实现十分复杂, 失去了树状数组本身简洁的优势

所以不如写线段树 👇

线段树

template <int maxn, typename val_t>
struct SegmentTree {
    struct Node {
        val_t sum;
        val_t tag; bool cov;
    } tr[maxn << 2];

    inline void pushUp (int now) {
        tr[now].sum = tr[now << 1].sum + tr[now << 1 | 1].sum;
    }

    inline void update (int now, int l, int r, val_t val) {
        tr[now].sum += val * (r - l + 1);
        tr[now].tag += val;
        tr[now].cov = true;
    }

    inline void pushDown (int now, int l, int r) {
        if (not tr[now].cov) { return; }
        int mid = (l + r) >> 1;
        update (now << 1, l, mid, tr[now].tag);
        update (now << 1 | 1, mid + 1, r, tr[now].tag);
        tr[now].tag = 0; tr[now].cov = false;
    }

    void build (int now, int l, int r) {
        if (l == r) {
            tr[now] = Node { a[l], 0, false };
            return;
        }

        int mid = (l + r) >> 1;
        build (now << 1, l, mid);
        build (now << 1 | 1, mid + 1, r);

        pushUp (now);
    }

    void modify (int now, int l, int r, int L, int R, val_t val) {
        if (L <= l and r <= R) { update (now, l, r, val); return; } 

        pushDown (now, l, r);
        int mid = (l + r) >> 1;
        if (L <= mid) { modify (now << 1, l, mid, L, R, val); }
        if (R > mid) { modify (now << 1 | 1, mid + 1, r, L, R, val); }
        pushUp (now);   
    }

    val_t query (int now, int l, int r, int L, int R) {
        if (L <= l and r <= R) { return tr[now].sum; }

        pushDown (now, l, r);
        int mid = (l + r) >> 1;
        val_t res = 0;
        if (L <= mid) { res += query (now << 1, l, mid, L, R); }
        if (R > mid) { res += query (now << 1 | 1, mid + 1, r, L, R); }

        return res;
    }
};

使用的时候, 只需要 SegmentTree<maxn, i64> tr 就行

权值线段树

template <int maxn, typename val_t>
struct SegmentTree {
    struct Node {
        int lson, rson;
        val_t sum;
    } tr[maxn << 4 + 5];

    int root;

    int tot;
    SegmentTree () { tot = 0; }

    inline void pushUp (int now) { tr[now].sum = tr[tr[now].lson].sum + tr[tr[now].rson].sum; }

    void modify (int &now, val_t l, val_t r, val_t pos, val_t val) {
        if (not now) { now = ++tot; }
        if (l == r) { tr[now].sum += val; return; }

        val_t mid = (l + r) >> 1;
        if (pos <= mid) { modify (tr[now].lson, l, mid, pos, val); }
        if (pos > mid) { modify (tr[now].rson, mid + 1, r, pos, val); }

        pushUp (now);
    }

    val_t query (int now, val_t l, val_t r, val_t L, val_t R) {
        if (not now) { return 0; }
        if (L <= l and r <= R) { return tr[now].sum; }

        val_t mid = (l + r) >> 1;
        val_t res = 0;
        if (L <= mid) { res += query (tr[now].lson, l, mid, L, R); }
        if (R > mid) { res += query (tr[now].rson, mid + 1, r, L, R); }
        return res;
     }
};

可持久化线段树

这里先只写一个可持久化数组

template <int maxn, typename val_t>
struct PresistentArray {
    struct Node {
        int ls, rs;
        val_t val;
    } tr[maxn << 5];

    int tot, root[maxn];
    inline int newNode (Node old = Node { 0, 0, 0 }) { tr[++tot] = old; return tot; }

    void build (int &now, int l, int r) {
        now = newNode ();
        if (l == r) { tr[now].val = a[l]; return; }

        int mid = (l + r) >> 1;
        build (tr[now].ls, l, mid);
        build (tr[now].rs, mid + 1, r);
    }

    void modify (int &now, int old, int l, int r, int pos, val_t val) {
        now = newNode (tr[old]);
        if (l == r) { tr[now].val = val; return; }

        int mid = (l + r) >> 1;
        if (pos <= mid) { modify (tr[now].ls, tr[old].ls, l, mid, pos, val); }
        if (pos > mid) { modify (tr[now].rs, tr[old].rs, mid + 1, r, pos, val); }
    }

    val_t query (int now, int l, int r, int pos) {
        if (not now) { return 0; }
        if (l == r) { return tr[now].val; }

        int mid = (l + r) >> 1;
        if (pos <= mid) { return query (tr[now].ls, l, mid, pos); }
        if (pos > mid) { return query (tr[now].rs, mid + 1, r, pos); }
        return 0;
    }
};

平衡树

FHQ-Treap

普通平衡树

template <int maxn, typename val_t>
struct FhqTreap {
    struct Node {
        int ls, rs;
        val_t val;
        unsigned long long key;
        int size;
    } tr[maxn];

    std::mt19937 rnd;

    int tot, root;
    inline int newNode (int val) {
        tr[++tot] = Node { 0, 0, val, rnd (), 1 };
        return tot;
    }

    inline void update (int now) { tr[now].size = tr[tr[now].ls].size + tr[tr[now].rs].size + 1; }

    FhqTreap () { tot = 0; }

    void split (int now, val_t val, int &x, int &y) {
        if (not now) {
            x = 0; y = 0;
        } else if (tr[now].val <= val) {
            x = now; split (tr[now].rs, val, tr[now].rs, y);
            update (x);
        } else {
            y = now; split (tr[now].ls, val, x, tr[now].ls);
            update (y);
        }
    }

    int merge (int x, int y) {
        if (not x or not y) {
            return x | y;
        } else if (tr[x].key < tr[y].key) {
            tr[x].rs = merge (tr[x].rs, y);
            update (x);
            return x;
        } else {
            tr[y].ls = merge (x, tr[y].ls);
            update (y);
            return y;
        }
    }

    inline void insert (val_t val) {
        int x, y; split (root, val, x, y);
        root = merge (merge (x, newNode (val)), y);
    }

    inline void remove (val_t val) {
        int x, y, z;
        split (root, val, x, y);
        split (x, val - 1, x, z);
        z = merge (tr[z].ls, tr[z].rs);
        root = merge (merge (x, z), y);
    }

    inline val_t pre (val_t val) {
        int x, y; split (root, val - 1, x, y);
        
        int now = x;
        while (tr[now].rs) { now = tr[now].rs; }
        
        root = merge (x, y);
        return tr[now].val;
    }

    inline val_t nxt (val_t val) {
        int x, y; split (root, val, x, y);
        
        int now = y;
        while (tr[now].ls) { now = tr[now].ls; }

        root = merge (x, y);
        return tr[now].val;
    }

    inline int get_rank (val_t val) {
        int x, y; split (root, val - 1, x, y);
        int rank = tr[x].size + 1;
        root = merge (x, y);
        return rank;
    }

    inline val_t get_val (int rank) {
        int now = root;
        while (true) {
            if (tr[tr[now].ls].size + 1 == rank) { return tr[now].val; }
            else if (tr[tr[now].ls].size >= rank) { now = tr[now].ls; }
            else { rank -= tr[tr[now].ls].size + 1; now = tr[now].rs; }
        }
        return -1;
    }
};

树

树链剖分

核心部分代码不长

int fa[maxn], siz[maxn], son[maxn], dep[maxn];
void build_tree (int now) {
	siz[now] = 1;
	for (int i = last[now]; i; i = es[i].pre) {
		int t = es[i].v;
		if (t == fa[now]) { continue; }
		fa[t] = now;
		dep[t] = dep[now] + 1;
		build_tree (t);
		siz[now] += siz[t];
		if (siz[t] > siz[son[now]]) { son[now] = t; }
	}
}

int top[maxn], dfn[maxn], dpos, rnk[maxn];
// int bottom[maxn];
void tree_decomp (int now, int topnow) {
	dfn[now] = ++dpos;
	rnk[dfn[now]] = now;
	top[now] = topnow;
	// bottom[now] = dfn[now];

	if (not son[now]) { return; }
	tree_decomp (son[now], topnow);
	// bottom[now] = std::max (bottom[now], bottom[son[now]]);

	for (int i = last[now]; i; i = es[i].pre) {
		int t = es[i].v;
		if (t == fa[now]) { continue; }
		if (t == son[now]) { continue; }

		tree_decomp (t, t);
		// bottom[now] = std::max (bottom[now], bottom[t]);
	}
}

子树内的信息

一般会像上面注释里面一样维护一个 bottom[u] 表示以 $u$ 为根的子树中最大的 $dfn$

然后就可以

inline i64 subtreeQuery (int x) {
	return tr.query (1, 1, n, dfn[x], bottom[x]);
}

修改同理

路径上的信息

直接跳链即可

inline void chainModify (int x, int y, i64 val) {
	while (top[x] != top[y]) {
		if (dep[top[x]] > dep[top[y]]) {
			tr.modify (1, 1, n, dfn[top[x]], dfn[x], val);
			x = fa[top[x]];
		} else {
			tr.modify (1, 1, n, dfn[top[y]], dfn[y], val);
			y = fa[top[y]];
		}
	}
	if (dfn[x] > dfn[y]) { std::swap (x, y); }
	tr.modify (1, 1, n, dfn[x], dfn[y], val);
}

查询同理

lca

同样是直接跳链

inline int lca (int u, int v) {
	while (top[u] != top[v]) {
		if (dep[top[u]] > dep[top[v]]) {
			u = fa[top[u]];
		} else {
			v = fa[top[v]];
		}
	}
	return dep[u] < dep[v] ? u : v;
}

淀粉质

inline void addEdge (int u, int v, int w) {
	es[++cnt] = Edge { u, v, last[u], w };
	last[u] = cnt;
}

int sum;
std::bitset<maxn> removed;

int root;
int maxpart[maxn];
int siz[maxn];

void getRoot (int now, int fa) {
	siz[now] = 1; 
	maxpart[now] = 0;
	for (int i = last[now]; i; i = es[i].pre) {
		int t = es[i].v;
		if (t == fa) { continue; }
		if (removed[t])	{ continue; }

		getRoot (t, now);
		siz[now] += siz[t];
		maxpart[now] = std::max (maxpart[now], siz[t]);
	}
	maxpart[now] = std::max (maxpart[now], sum - siz[now]);
	if (maxpart[now] < maxpart[root]) { root = now; }
}

int disStack[maxn], dpos;
int removeStack[maxn], rpos;

int dis[maxn];
void getDis (int now, int fa) {
	disStack[++dpos] = dis[now];
	for (int i = last[now]; i; i = es[i].pre) {
		int t = es[i].v;
		if (t == fa) { continue; }
		if (removed[t]) { continue; }
		
		dis[t] = dis[now] + es[i].w;
		getDis (t, now);
	}
}

const int maxv = 100000005;
std::bitset<maxv> exist;

void solve (int now) {
	exist[0] = true;

	for (int i = last[now]; i; i = es[i].pre) {
		int t = es[i].v;
		if (removed[t]) { continue; }

		dis[t] = es[i].w;
		getDis (t, now);

		for (int j = 1; j <= dpos; j++) {
			for (auto &q : qs) {
				if (q.k - disStack[j] >= 0) { q.ans |= exist[q.k - disStack[j]]; }
			}
		}

		while (dpos) {
			int top = disStack[dpos--];
			exist[top] = true;
			removeStack[++rpos] = top;
		}
	}

	while (rpos) {
		int top = removeStack[rpos--];
		exist[top] = false;
	}
}

inline void divide (int now) {
	removed[now] = true;
	solve (now);

	for (int i = last[now]; i; i = es[i].pre) {
		int t = es[i].v;
		if (removed[t]) { continue; }

		sum = siz[t];
		maxpart[root] = 0x3f3f3f3f;
		getRoot (t, now);
		getRoot (root, now); // 实际上在getSiz

		divide (root);
	}
}