Tarjan's Algorithm for Strongly Connnected Components

namespace TarjanSCC {
    int dfn[N], low[N], index, colorCount;
    int comp[N], size[N], value[N];
    bool inStack[N];
    stack<int> stk;
    vector<int> graph[N];

    void tarjan(int u) {
        dfn[u] = low[u] = ++index;
        stk.push(u);
        inStack[u] = true;

        for (int v : graph[u]) {
            if (!dfn[v]) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (inStack[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }

        if (dfn[u] == low[u]) {
            int node;
            colorCount++;
            do {
                node = stk.top(); stk.pop();
                comp[node] = colorCount;
                size[colorCount]++;
                value[colorCount] += a[node];
                inStack[node] = false;
            } while (node != u);
        }
    }
}

Tree Chain Decomposition for LCA Queries

struct TreeLCA {
    int sz[N], heavy[N], parent[N], depth[N], topChain[N];
    vector<int> adj[N];

    void dfs1(int u, int p) {
        sz[u] = 1;
        parent[u] = p;
        depth[u] = depth[p] + 1;
        for (int v : adj[u]) {
            if (v == p) continue;
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[heavy[u]]) heavy[u] = v;
        }
    }

    void dfs2(int u, int chainTop) {
        topChain[u] = chainTop;
        if (heavy[u]) dfs2(heavy[u], chainTop);
        for (int v : adj[u]) {
            if (v == parent[u] || v == heavy[u]) continue;
            dfs2(v, v);
        }
    }

    int queryLCA(int u, int v) {
        while (topChain[u] != topChain[v]) {
            if (depth[topChain[u]] < depth[topChanin[v]]) swap(u, v);
            u = parent[topChain[u]];
        }
        return depth[u] < depth[v] ? u : v;
    }
};

Matrix Exponentiation

struct Matrix {
    int mat[3][3], rows, cols;
    Matrix(int r = 2, int c = 2) : rows(r), cols(c) {
        memset(mat, 0, sizeof(mat));
    }

    Matrix operator*(const Matrix& other) const {
        Matrix res(rows, other.cols);
        for (int i = 1; i <= rows; ++i)
            for (int j = 1; j <= other.cols; ++j)
                for (int k = 1; k <= cols; ++k)
                    res.mat[i][j] = (res.mat[i][j] + 1LL * mat[i][k] * other.mat[k][j] % mod) % mod;
        return res;
    }
};

Matrix matrixPow(Matrix base, int exp) {
    Matrix result(base.rows, base.cols);
    for (int i = 1; i <= base.rows; ++i)
        result.mat[i][i] = 1;

    while (exp) {
        if (exp & 1) result = result * base;
        base = base * base;
        exp >>= 1;
    }
    return result;
}

FHQ Treap with Split-Merge Operations

struct FHQTreap {
    struct Node {
        int left, right, key, priority, size;
    } tree[N];

    int root = 0, nodeCount = 0;

    void updateSize(int k) {
        tree[k].size = tree[tree[k].left].size + tree[tree[k].right].size + 1;
    }

    void split(int node, int val, int &leftRoot, int &rightRoot) {
        if (!node) {
            leftRoot = rightRoot = 0;
            return;
        }
        if (tree[node].key <= val) {
            leftRoot = node;
            split(tree[node].right, val, tree[node].right, rightRoot);
        } else {
            rightRoot = node;
            split(tree[node].left, val, leftRoot, tree[node].left);
        }
        updateSize(node);
    }

    int merge(int left, int right) {
        if (!left || !right) return left | right;
        if (tree[left].priority > tree[right].priority) {
            tree[left].right = merge(tree[left].right, right);
            updateSize(left);
            return left;
        } else {
            tree[right].left = merge(left, tree[right].left);
            updateSize(right);
            return right;
        }
    }

    void insert(int val) {
        int l, r;
        split(root, val, l, r);
        tree[++nodeCount] = {0, 0, val, rand(), 1};
        root = merge(merge(l, nodeCount), r);
    }

    void remove(int val) {
        int l, m, r;
        split(root, val, l, r);
        split(l, val - 1, l, m);
        m = merge(tree[m].left, tree[m].right);
        root = merge(merge(l, m), r);
    }
};

Splay-like Reversal with FHQ Treap

This variant supports lazy reversal operations on a sequence.

struct ReversibleTreap {
    struct Node {
        int left, right, value, weight, size;
        bool reversed;
    } tr[N];

    int root = 0, cnt = 0;

    void pushDown(int k) {
        if (tr[k].reversed) {
            swap(tr[k].left, tr[k].right);
            tr[tr[k].left].reversed ^= 1;
            tr[tr[k].right].reversed ^= 1;
            tr[k].reversed = 0;
        }
    }

    void reverseRange(int l, int r) {
        int x, y, z;
        split(root, r, x, z);
        split(x, l - 1, x, y);
        tr[y].reversed ^= 1;
        root = merge(x, merge(y, z));
    }

    void inorderPrint(int k) {
        if (!k) return;
        pushDown(k);
        inorderPrint(tr[k].left);
        cout << tr[k].value << " ";
        inorderPrint(tr[k].right);
    }
};

Segment Tree for Range Maximum Queries

struct SegmentTree {
    struct Node {
        int left, right, maxVal;
    } nodes[N << 2];

    void pushUp(int k) {
        nodes[k].maxVal = max(nodes[k << 1].maxVal, nodes[k << 1 | 1].maxVal);
    }

    void build(int k, int l, int r, int arr[]) {
        nodes[k].left = l; nodes[k].right = r;
        if (l == r) {
            nodes[k].maxVal = arr[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(k << 1, l, mid, arr);
        build(k << 1 | 1, mid + 1, r, arr);
        pushUp(k);
    }

    int queryMax(int k, int l, int r) {
        if (nodes[k].left >= l && nodes[k].right <= r)
            return nodes[k].maxVal;

        int mid = (nodes[k].left + nodes[k].right) >> 1;
        int result = -INF;
        if (l <= mid) result = max(result, queryMax(k << 1, l, r));
        if (r > mid) result = max(result, queryMax(k << 1 | 1, l, r));
        return result;
    }
};

Sparse Table for Static RMQ

struct SparseTable {
    int st[N][LOG], index[N][LOG];

    void build(int arr[], int n) {
        for (int i = 1; i <= n; ++i) {
            st[i][0] = arr[i];
            index[i][0] = i;
        }
        for (int j = 1; (1 << j) <= n; ++j)
            for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
                int left = st[i][j-1], right = st[i + (1 << (j-1))][j-1];
                st[i][j] = max(left, right);
                index[i][j] = arr[left] > arr[right] ? left : right;
            }
    }

    int queryMax(int l, int r) {
        int k = log2(r - l + 1);
        return max(st[l][k], st[r - (1 << k) + 1][k]);
    }
};

Disjoint Set Union with Path Compression and Size Merging

namespace DSU {
    int parent[N], setSize[N];

    void initialize(int n) {
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
            setSize[i] = 1;
        }
    }

    int findRoot(int x) {
        return parent[x] == x ? x : parent[x] = findRoot(parent[x]);
    }

    void unite(int x, int y) {
        int rx = findRoot(x), ry = findRoot(y);
        if (rx == ry) return;
        if (setSize[rx] < setSize[ry]) swap(rx, ry);
        parent[ry] = rx;
        setSize[rx] += setSize[ry];
    }
}

Fast Input/Output Utilities

namespace FastIO {
    int read() {
        int x = 0; bool neg = false;
        char c = getchar();
        while (c < '0' || c > '9') {
            if (c == '-') neg = true;
            c = getchar();
        }
        while (c >= '0' && c <= '9') {
            x = x * 10 + (c ^ 48);
            c = getchar();
        }
        return neg ? -x : x;
    }

    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

AC Automaton for Multi-Pattern Matching

struct ACAutomaton {
    int trie[N][26], fail[N], count[N], nodeCount = 0;

    void insert(string &s) {
        int u = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!trie[u][idx]) trie[u][idx] = ++nodeCount;
            u = trie[u][idx];
        }
        count[u]++;
    }

    void buildFail() {
        queue<int> q;
        for (int i = 0; i < 26; ++i)
            if (trie[0][i]) q.push(trie[0][i]);

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 0; i < 26; ++i) {
                int &v = trie[u][i];
                if (v) {
                    fail[v] = trie[fail[u]][i];
                    q.push(v);
                } else {
                    v = trie[fail[u]][i];
                }
            }
        }
    }

    int match(string &text) {
        int u = 0, total = 0;
        for (char c : text) {
            u = trie[u][c - 'a'];
            for (int v = u; v && count[v] != -1; v = fail[v])
                total += count[v], count[v] = -1;
        }
        return total;
    }
};

KMP Algorithm for Pattern Matching

void computeLPS(string pattern, int lps[]) {
    int len = 0, i = 1;
    lps[0] = 0;
    while (i < pattern.size()) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
    }
}

int kmpSearch(string text, string pattern) {
    int n = text.size(), m = pattern.size();
    int lps[m];
    computeLPS(pattern, lps);

    int i = 0, j = 0, count = 0;
    while (i < n) {
        if (text[i] == pattern[j]) i++, j++;
        if (j == m) {
            count++;
            j = lps[j - 1];
        } else if (i < n && text[i] != pattern[j]) {
            if (j != 0) j = lps[j - 1];
            else i++;
        }
    }
    return count;
}

Dinic's Algorithm for Max Flow

struct DinicMaxFlow {
    struct Edge { int to, cap, flow; };
    vector<Edge> edges;
    vector<int> adj[N];
    int level[N], ptr[N];

    void addEdge(int u, int v, int cap) {
        edges.push_back({v, cap, 0});
        edges.push_back({u, 0, 0});
        adj[u].push_back(edges.size() - 2);
        adj[v].push_back(edges.size() - 1);
    }

    bool bfs(int s, int t) {
        fill(level, level + N, -1);
        queue<int> q;
        q.push(s);
        level[s] = 0;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i : adj[u]) {
                Edge &e = edges[i];
                if (level[e.to] == -1 && e.flow < e.cap) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    int dfs(int u, int t, int flow) {
        if (u == t || !flow) return flow;
        for (int &i = ptr[u]; i < adj[u].size(); ++i) {
            Edge &e = edges[adj[u][i]];
            if (level[e.to] == level[u] + 1) {
                int pushed = dfs(e.to, t, min(flow, e.cap - e.flow));
                if (pushed) {
                    e.flow += pushed;
                    edges[adj[u][i]^1].flow -= pushed;
                    return pushed;
                }
            }
        }
        return 0;
    }

    int maxFlow(int s, int t) {
        int total = 0;
        while (bfs(s, t)) {
            fill(ptr, ptr + N, 0);
            while (int pushed = dfs(s, t, INF))
                total += pushed;
        }
        return total;
    }
};

Edmonds-Karp Algorithm with Min-Cost Flow Extension

struct EKMinCostFlow {
    struct Edge { int to, cap, flow, cost; };
    vector<Edge> edges;
    vector<int> adj[N];
    int dist[N], prevNode[N], prevEdge[N];
    bool inQueue[N];

    bool spfa(int s, int t) {
        fill(dist, dist + N, INF);
        queue<int> q;
        q.push(s);
        dist[s] = 0;
        inQueue[s] = true;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            inQueue[u] = false;
            for (int i : adj[u]) {
                Edge &e = edges[i];
                if (e.flow < e.cap && dist[e.to] > dist[u] + e.cost) {
                    dist[e.to] = dist[u] + e.cost;
                    prevNode[e.to] = u;
                    prevEdge[e.to] = i;
                    if (!inQueue[e.to]) {
                        q.push(e.to);
                        inQueue[e.to] = true;
                    }
                }
            }
        }
        return dist[t] < INF;
    }

    pair<int, int> solve(int s, int t) {
        int flow = 0, cost = 0;
        while (spfa(s, t)) {
            int f = INF;
            for (int u = t; u != s; u = prevNode[u])
                f = min(f, edges[prevEdge[u]].cap - edges[prevEdge[u]].flow);

            for (int u = t; u != s; u = prevNode[u]) {
                edges[prevEdge[u]].flow += f;
                edges[prevEdge[u]^1].flow -= f;
            }
            flow += f;
            cost += f * dist[t];
        }
        return {flow, cost};
    }
};

Lucas Theorem for Large Combinatorics Modulo Prime

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

long long factorial[N], inverse[N];

void precomputeFactorials(int mod) {
    factorial[0] = 1;
    for (int i = 1; i < mod; ++i)
        factorial[i] = (factorial[i-1] * i) % mod;
    inverse[mod-1] = modPow(factorial[mod-1], mod - 2, mod);
    for (int i = mod-2; i >= 0; --i)
        inverse[i] = (inverse[i+1] * (i+1)) % mod;
}

long long comb(int n, int r, int mod) {
    if (r < 0 || r > n) return 0;
    return ((factorial[n] * inverse[r]) % mod * inverse[n - r]) % mod;
}

long long lucas(int n, int r, int mod) {
    if (r == 0) return 1;
    return (comb(n % mod, r % mod, mod) * lucas(n / mod, r / mod, mod)) % mod;
}

Z-Algorithm for String Matching

vector<int> computeZArray(string s) {
    int n = s.length();
    vector<int> Z(n);
    int left = 0, right = 0;
    for (int i = 1; i < n; ++i) {
        if (i <= right)
            Z[i] = min(right - i + 1, Z[i - left]);
        while (i + Z[i] < n && s[Z[i]] == s[i + Z[i]])
            Z[i]++;
        if (i + Z[i] - 1 > right)
            left = i, right = i + Z[i] - 1;
    }
    return Z;
}

Gaussian Eilmination for Linear Systems

namespace GaussianElim {
    long double mat[500][500];
    int n;

    void solve() {
        for (int col = 1, row = 1; col <= n && row <= n; ++col, ++row) {
            int pivot = row;
            for (int i = row + 1; i <= n; ++i)
                if (abs(mat[i][col]) > abs(mat[pivot][col]))
                    pivot = i;

            swap(mat[pivot], mat[row]);

            if (abs(mat[row][col]) < EPS) {
                puts("No Solution");
                exit(0);
            }

            for (int j = col; j <= n + 1; ++j)
                mat[row][j] /= mat[row][col];

            for (int i = row + 1; i <= n; ++i)
                for (int j = n + 1; j >= col; --j)
                    mat[i][j] -= mat[i][col] * mat[row][j];
        }

        for (int i = n; i >= 1; --i)
            for (int j = i - 1; j >= 1; --j)
                mat[j][n+1] -= mat[i][n+1] * mat[j][i];
    }
};

Linear Basis for XOR Space Operations

namespace XorBasis {
    long long basis[64];
    int count = 0;

    void insert(long long x) {
        for (int i = 63; i >= 0; --i) {
            if (!(x & (1LL << i))) continue;
            if (!basis[i]) {
                basis[i] = x;
                count++;
                break;
            }
            x ^= basis[i];
        }
    }

    bool canRepresent(long long x) {
        for (int i = 63; i >= 0; --i)
            if (x & (1LL << i))
                x ^= basis[i];
        return x == 0;
    }

    long long getMaxXor(long long initial = 0) {
        long long result = initial;
        for (int i = 63; i >= 0; --i)
            if ((result ^ basis[i]) > result)
                result ^= basis[i];
        return result;
    }
};

Centroid Decomposition for Tree Queries

int getSize(int u, int parent, bool deleted[]) {
    if (deleted[u]) return 0;
    int total = 1;
    for (auto [v, w] : adj[u]) {
        if (v == parent) continue;
        total += getSize(v, u, deleted);
    }
    return total;
}

int findCentroid(int u, int parent, int total, bool deleted[], int &centroid) {
    if (deleted[u]) return 0;
    int sum = 1, maxSub = 0;
    for (auto [v, w] : adj[u]) {
        if (v == parent) continue;
        int sz = findCentroid(v, u, total, deleted, centroid);
        maxSub = max(maxSub, sz);
        sum += sz;
    }
    maxSub = max(maxSub, total - sum);
    if (maxSub <= total / 2) centroid = u;
    return sum;
}

Li-Chao Tree for Dynamic Line Insertion and Point Query

struct LiChaoTree {
    struct Line {
        long double k, b;
        long double eval(int x) { return k * x + b; }
    };

    Line tree[N];
    bool empty[N];

    void insertLine(int k, int l, int r, Line newLine) {
        if (empty[k]) {
            tree[k] = newLine;
            empty[k] = false;
            return;
        }

        int mid = (l + r) >> 1;
        bool leftBetter = newLine.eval(l) > tree[k].eval(l);
        bool midBetter = newLine.eval(mid) > tree[k].eval(mid);

        if (midBetter) swap(tree[k], newLine);

        if (l == r) return;
        if (leftBetter != midBetter)
            insertLine(k << 1, l, mid, newLine);
        else
            insertLine(k << 1 | 1, mid + 1, r, newLine);
    }

    long double query(int k, int l, int r, int pos) {
        if (l == r) return tree[k].eval(pos);
        int mid = (l + r) >> 1;
        long double res = tree[k].eval(pos);
        if (pos <= mid)
            res = max(res, query(k << 1, l, mid, pos));
        else
            res = max(res, query(k << 1 | 1, mid + 1, r, pos));
        return res;
    }
};