Graph

Dijkstra

template <typename T> struct Dijkstra {
    vector<T> dis;
    vector<int> par;

    Dijkstra(int n, T inf) {
        dis = vector<T>(n, inf);
        par = vector<int>(n, -1);
    }

    void run(const vector<vector<pair<int, T>>> &adj,
             const vector<int> &sources) {
        using Item = pair<T, int>;

        priority_queue<Item, vector<Item>, greater<Item>> que;
        for (auto u : sources) {
            dis[u] = 0;
            par[u] = u;
            que.push({dis[u], u});
        }

        while (!que.empty()) {
            auto [d, u] = que.top();
            que.pop();
            if (d > dis[u]) {
                continue;
            }

            for (auto [v, w] : adj[u]) {
                auto new_d = dis[u] + w;
                if (new_d < dis[v]) {
                    dis[v] = new_d;
                    par[v] = u;
                    que.push({dis[v], v});
                }
            }
        }
    }
};

https://cses.fi/problemset/result/6059594/

SegTree

#include <algorithm>
#include <iostream>
#include <vector>
#include <functional>
using namespace std;

template <typename S, typename F> struct LazySegTree {
    // lazy[u] != default_lazy <-> data[lch] and data[rch] are not up-to-date,
    // but data[u] is. lazy[u] == default_lazy <-> data[u], data[lch], data[rch]
    // are up-to-date.
    int NN;
    vector<S> data;
    vector<F> lazy;

    virtual S default_data() = 0;
    virtual F default_lazy() = 0;
    virtual S op(S a, S b) = 0;
    virtual S apply_lazy(F lazy, S val, int u, int l, int r) = 0;
    virtual F merge_lazy(F parent, F child) = 0;

    LazySegTree() = default;

    // Calling virtual functions in constructor is not allowed.
    // Therefore, we use this function instead.
    void build_from_vector(const vector<S> &A) {
        this->NN = 1;
        while (this->NN < int(A.size())) {
            this->NN <<= 1;
        }
        this->data = vector<S>(2 * this->NN, this->default_data());
        this->lazy = vector<F>(2 * this->NN, this->default_lazy());
        for (int i = 0; i < int(A.size()); i++) {
            this->data[this->NN - 1 + i] = A[i];
        }
        for (int u = this->NN - 2; u >= 0; u--) {
            this->data[u] =
                this->op(this->data[u * 2 + 1], this->data[u * 2 + 2]);
        }
    }

    // Apply lazy[u] to lch and rch, so data[lch] and data[rch] are updated.
    // Merge lazy[u] into lazy[lch] and lazy[rch]
    void push(int u, int l, int r) {
        if (lazy[u] == this->default_lazy())
            return;
        int m = (l + r) / 2;
        int lch = u * 2 + 1;
        int rch = u * 2 + 2;
        this->data[lch] =
            this->apply_lazy(this->lazy[u], this->data[lch], lch, l, m);
        this->data[rch] =
            this->apply_lazy(this->lazy[u], this->data[rch], rch, m, r);
        this->lazy[lch] = this->merge_lazy(this->lazy[u], this->lazy[lch]);
        this->lazy[rch] = this->merge_lazy(this->lazy[u], this->lazy[rch]);
        this->lazy[u] = this->default_lazy();
    }

    S prod(int a, int b, int u = -1, int l = -1, int r = -1) {
        if (u == -1)
            u = 0, l = 0, r = this->NN;
        if (l >= b || r <= a)
            return this->default_data();
        if (l >= a && r <= b)
            return this->data[u];
        int m = (l + r) / 2;
        this->push(u, l, r);
        S res1 = this->prod(a, b, u * 2 + 1, l, m);
        S res2 = this->prod(a, b, u * 2 + 2, m, r);
        return this->op(res1, res2);
    }

    void apply(int a, int b, F x, int u = -1, int l = -1, int r = -1) {
        if (u == -1)
            u = 0, l = 0, r = this->NN;
        if (l >= b || r <= a)
            return;
        if (l >= a && r <= b) {
            this->data[u] = this->apply_lazy(x, this->data[u], u, l, r);
            this->lazy[u] = this->merge_lazy(x, this->lazy[u]);
            return;
        }
        int m = (l + r) / 2;
        this->push(u, l, r);
        this->apply(a, b, x, u * 2 + 1, l, m);
        this->apply(a, b, x, u * 2 + 2, m, r);
        this->data[u] = this->op(this->data[u * 2 + 1], this->data[u * 2 + 2]);
    }

    int find_first_of(const function<bool(S, int, int, int)> &f, int u = -1,
                      int l = -1, int r = -1) {
        if (u == -1)
            u = 0, l = 0, r = this->NN;
        if (!f(this->data[u], u, l, r))
            return -1;
        if (r - l == 1)
            return u - (this->NN - 1);
        int m = (l + r) / 2;
        int idx1 = this->find_first_of(f, u * 2 + 1, l, m);
        if (idx1 != -1)
            return idx1;
        int idx2 = this->find_first_of(f, u * 2 + 2, m, r);
        if (idx2 != -1)
            return idx2;
        return -1;
    }
};
 
using S = int;
using F = int;
struct SegTree : LazySegTree<S, F> {
    S default_data() { return 0x3f3f3f3f; }
    F default_lazy() { return 0; }
    S op(S lch, S rch) { return min(lch, rch); }
    S apply_lazy(F lazy, S val, int u, int l, int r) {
        return lazy + val;
    }
    F merge_lazy(F parent, F child) { return parent + child; }
};

驗題：

• https://atcoder.jp/contests/abc223/submissions/33287093
• https://judge.yosupo.jp/submission/104918

Tree Diamter

https://hackmd.io/9KrxOEwRRA6LYrfn1NA9pQ?view#Tree-Diameter

tuple<vector<int>, vector<int>, vector<int>> bfs(const vector<vector<int>> &G,
                                                 int root, int parent) {
    int N = G.size();
    auto vis = vector<int>();
    auto par = vector(N, -1);
    auto dep = vector(N, -1);
    auto que = queue<tuple<int, int>>();
 
    par[root] = parent;
    dep[root] = 0;
    que.push({root, parent});
 
    while (que.size() > 0) {
        auto [u, p] = que.front();
        que.pop();
        vis.push_back(u);
        for (auto v : G[u]) {
            if (v != p) {
                par[v] = u;
                dep[v] = dep[u] + 1;
                que.push({v, u});
            }
        }
    }
 
    return {vis, par, dep};
}

int main() {
    auto [vis, par, dep] = bfs(G, 0, -1);
    int s = vis.back();
    auto [s_vis, s_par, s_dep] = bfs(G, s, -1);
    int t = s_vis.back();
    
    return 0;
}

Prefix

template <typename T> struct Prefix2D {
    vector<vector<T>> pref;

    Prefix2D() = default;

    Prefix2D(const vector<vector<T>> &A) {
        int N = A.size();
        int M = A[0].size();
        pref = vector(N, vector<T>(M, 0));
        pref[0][0] = A[0][0];
        for (int r = 1; r < N; r++) {
            pref[r][0] = pref[r - 1][0] + A[r][0];
        }
        for (int c = 1; c < M; c++) {
            pref[0][c] = pref[0][c - 1] + A[0][c];
        }
        for (int r = 1; r < N; r++) {
            for (int c = 1; c < M; c++) {
                pref[r][c] = pref[r][c - 1] + pref[r - 1][c] -
                             pref[r - 1][c - 1] + A[r][c];
            }
        }
    }

    // [r1, r2] x [c1, c2]
    T query(int r1, int r2, int c1, int c2) {
        T ans = pref[r2][c2];
        if (r1 >= 1)
            ans -= pref[r1 - 1][c2];
        if (c1 >= 1)
            ans -= pref[r2][c1 - 1];
        if (r1 >= 1 && c1 >= 1)
            ans += pref[r1 - 1][c1 - 1];
        return ans;
    }
};

BIT

template <typename T> struct BIT {
    vector<T> data;

    BIT(int n) { data = vector<T>(n, 0); }

    void add(int idx, T val) {
        for (int i = idx + 1; i <= data.size() - 1; i += (i & (-i))) {
            data[i] = data[i] + val;
        }
    }

    T prefix(int idx) {
        T res = 0;
        for (int i = idx + 1; i > 0; i -= (i & -i)) {
            res = res + data[i];
        }
        return res;
    }

    T sum(int l, int r) { // l..r
        T val = prefix(r - 1);
        if (l != 0) {
            val -= prefix(l - 1);
        }
        return val;
    }
};

https://atcoder.jp/contests/abc294/submissions/39908415

Utility

Argsort

template <typename T> vector<int> argsort(const vector<T> &v) {
    vector<pair<T, int>> data;
    for (int i = 0; i < int(v.size()); i++) {
        data.push_back({v[i], i});
    }
    sort(data.begin(), data.end());
    vector<int> indices;
    for (auto &&[_, i] : data) {
        indices.push_back(i);
    }
    return indices;
}

Print Vector

template <typename T>
string join(const vector<T> &arr, const string &seperator = " ") {
    ostringstream oss;
    for (size_t i = 0; i < arr.size(); i++) {
        if (i != 0) {
            oss << seperator;
        }
        oss << arr[i];
    }
    return oss.str();
}

Print Map

template <typename K, typename V>
ostream &operator<<(ostream &out, const map<K, V>& m) {
    out << "{ ";
    for (auto &[k, v] : m) {
        out << k << ": " << v << ", ";
    }
    out << "}";
    return out;
}

Print Tuple

template <typename TupType, size_t... I>
ostream &tuple_print(ostream &out, const TupType &_tup, index_sequence<I...>) {
    out << "(";
    (..., (out << (I == 0 ? "" : ", ") << get<I>(_tup)));
    out << ")";
    return out;
}
template <typename... T> ostream &operator<<(ostream &out, const tuple<T...> &t) {
    return tuple_print(out, t, make_index_sequence<sizeof...(T)>());
}

Print Pair

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2>& p) {
    out << "( " << p.first << ", " << p.second << " )";
    return out;
}

Numbers

Euclidean Division

pair<ll, ll> euclid_div(ll a, ll b) {
    ll q = a / b;
    ll r = a % b;
    if (r < 0) {
        r += b;
        q -= 1;
    }
    return {q, r};
}

GCD

ll gcd(ll a, ll b) {
    // gcd(x, 0) = x
    // gcd(a, b) = gcd(b, r)
    while (b != 0) {
        ll r = a % b;
        a = b;
        b = r;
    }
    return a;
}

ExtGCD

tuple<ll, ll, ll> extgcd(ll a, ll b) {
    if (b == 0) {
        return {1, 0, a};
    } else {
        auto [x1, y1, g] = extgcd(b, (a % b + b) % b);
        return {y1, x1 - a / b * y1, g};
    }
}

Sieve Of Eratosthenes

using ll = long long;
using pll = pair<ll, ll>;

struct SieveOfEratosthenes {
    vector<bool> is_prime;
    vector<ll> primes;

    SieveOfEratosthenes(ll V) {
        is_prime = vector<bool>(V + 1, true);
        primes = vector<ll>();
        for (ll i = 2; i <= V; i ++) {
            if (is_prime[i]) {
                primes.push_back(i);
                for (ll j = i * i; j <= V; j += i) {
                    is_prime[j] = false;
                }
            }
        }
    }

    vector<pll> factorize(ll x) {
        if (x <= 1) {
            throw invalid_argument("x shoule be > 1");
        }
        auto result = vector<pll>();
        for (auto p : primes) {
            ll exp = 0;
            while (x % p == 0) {
                exp++;
                x = x / p;
            }
            if (exp > 0) {
                result.push_back(pll(p, exp));
            }
            if (p * p > x) {
                break;
            }
        }
        if (x > 1) {
            result.push_back(pll(x, 1));
        }
        return result;
    }
};

Combination

template <typename T> struct CombTool {
    vector<T> fact;
    vector<T> finv;
 
    CombTool(int V) {
        fact = vector<T>(V, 1);
        finv = vector<T>(V, 1);
        for (int i = 1; i < V; i++) {
            fact[i] = fact[i - 1] * i;
        }
        finv[V - 1] = fact.back().inv();
        for (int i = V - 2; i >= 0; i--) {
            finv[i] = finv[i + 1] * (i + 1);
        }
    }
 
    T comb(int a, int b) { return fact[a] * finv[b] * finv[a - b]; }
    T perm(int a, int b) { return fact[a] * finv[a - b]; }
    T hcomb(int a, int b) { return comb(a + b - 1, b); }
};

Heavy Light Decomposition

struct HLD {
    vector<int> size;
    vector<int> depth;
    vector<int> heavy;
    vector<int> parent;
    vector<int> top;
    vector<int> tour;
    vector<int> t_enter;
    vector<int> t_leave;
 
    HLD(const vector<vector<int>> &adj, int root) {
        int N = adj.size();
        const int inf = 0x3f3f3f3f;
 
        // Find size, depth, heavy, parent by DFS
        {
            size = vector<int>(N, 1);
            depth = vector<int>(N, 0);
            heavy = vector<int>(N, inf);
            parent = vector<int>(N, inf);
            auto stack = vector<pair<char, int>>{{'l', root}, {'e', root}};
            depth[root] = 0;
            parent[root] = root;
            while (!stack.empty()) {
                auto [cmd, u] = stack.back();
                stack.pop_back();
                if (cmd == 'l') {
                    size[u] = 1;
                    heavy[u] = inf;
                    for (auto v : adj[u]) {
                        if (v != parent[u]) {
                            size[u] += size[v];
                            if (heavy[u] == inf || size[v] > size[heavy[u]]) {
                                heavy[u] = v;
                            }
                        }
                    }
                } else {
                    for (auto v : adj[u]) {
                        if (parent[v] == inf) {
                            parent[v] = u;
                            depth[v] = depth[u] + 1;
                            stack.push_back({'l', v});
                            stack.push_back({'e', v});
                        }
                    }
                }
            }
        }
 
        // Find top, tour, t_enter, t_leave by DFS
        {
            int time = 0;
            top = vector<int>(N, inf);
            tour = vector<int>(N, inf);
            t_enter = vector<int>(N, inf);
            t_leave = vector<int>(N, inf);
            auto stack = vector<pair<char, int>>{{'l', root}, {'e', root}};
            top[root] = root;
            while (!stack.empty()) {
                auto [cmd, u] = stack.back();
                stack.pop_back();
                if (cmd == 'l') {
                    t_leave[u] = time;
                } else {
                    t_enter[u] = time;
                    tour[time] = u;
                    time++;
                    for (auto v : adj[u]) {
                        if (v != parent[u]) {
                            // heavy edge / light edge
                            top[v] = ((v == heavy[u]) ? top[u] : v);
                            stack.push_back({'l', v});
                            stack.push_back({'e', v});
                        }
                    }
                }
            }
        }
    }
 
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (depth[top[u]] > depth[top[v]]) {
                u = parent[top[u]];
            } else {
                v = parent[top[v]];
            }
        }
        return ((depth[u] < depth[v]) ? u : v);
    }
};

https://atcoder.jp/contests/abc294/submissions/39908415

Z algorithm

https://cp-algorithms.com/string/z-function.html

vector<int> zfunc(const string& S) {
    int N = S.length();
    vector<int> z(N, 0);
    int l = 0, r = 0;
    for (int i = 1; i < N; i++) {
        if (i <= r) {
            z[i] = min(r - i, z[i - l]);
        }
        while (i + z[i] < N && S[i + z[i]] == S[z[i]]) {
            z[i]++;
        }
        if (i + z[i] - 1 >= r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

Rolling Hash

https://cp-algorithms.com/string/string-hashing.html

#include <cassert>
using ll = long long;

ll powmod(ll a, ll b, ll m) {
    ll base = a;
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * base % m;
        }
        base = base * base % m;
        b >>= 1;
    }
    return res;
}

struct PolyHash {
    ll mod;
    ll base;
    vector<ll> powr;
    vector<ll> pinv;

    // N is max length; mod should be prime
    PolyHash(int N, ll base = 31, ll mod = 1e9 + 7) {
        this->base = base;
        this->mod = mod;
        powr = vector<ll>(N, 1);
        pinv = vector<ll>(N, 1);
        for (int i = 1; i < N; i++) {
            powr[i] = powr[i - 1] * base % mod;
        }
        pinv[N - 1] = powmod(powr[N - 1], mod - 2, mod);
        for (int i = N - 2; i >= 0; i--) {
            pinv[i] = pinv[i + 1] * base % mod;
        }
    }

    vector<ll> transform(const vector<int> &v) {
        for (auto && x : v) {
            assert (x != 0);
        }
        
        vector<ll> h(v.size());
        h[0] = v[0] % mod;
        for (size_t i = 1; i < v.size(); i++) {
            h[i] = (h[i - 1] + v[i] * powr[i] % mod) % mod;
        }
        return h;
    }

    ll substr(const vector<ll> &h, int l, int r) { // [l, r)
        if (l == 0) {
            return h[r - 1];
        } else {
            return ((h[r - 1] - h[l - 1] + mod) % mod) * pinv[l] % mod;
        }
    }
};

vector<int> string2vector(const string &s) {
    vector<int> v(s.length());
    for (size_t i = 0; i < s.length(); i++) {
        if (s[i] >= 'a' && s[i] <= 'z') {
            v[i] = s[i] - 'a' + 1;
        } else {
            v[i] = s[i] - 'A' + 1;
        }
    }
    return v;
}