compro_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub siro53/compro_library

:heavy_check_mark: data-structure/persistent/persistent-unionfind.hpp

Depends on

Verified with

Code

#pragma once

#include <algorithm>
#include <tuple>

#include "persistent-array.hpp"

struct PersistentUnionFind {
    PersistentArray<int> par;
    using Node = decltype(par)::Node;
    Node* root;

    explicit PersistentUnionFind(int n): par(std::vector<int>(n, -1)) {
        root = par.root;
    }
    // (leader, size)
    std::pair<int, int> leader_and_size(int u, Node* r) {
        int p = par.get(r, u);
        return (p < 0 ? std::make_pair(u, -p) : leader_and_size(p, r));
    }
    std::pair<int, int> leader_and_size(int u) {
        return leader_and_size(u, root);
    }
    inline int leader(int u, Node* r) { return leader_and_size(u, r).first; }
    inline int leader(int u) { return leader_and_size(u, root).first; }
    inline int size(int u, Node* r) { return leader_and_size(u, r).second; }
    inline int size(int u) { return leader_and_size(u, root).second; }
    inline bool same(int u, int v, Node* r) { return (leader(u, r) == leader(v, r)); }
    inline bool same(int u, int v) { return same(u, v, root); }
    bool merge(int u, int v, Node* r) {
        int sz_u, sz_v;
        std::tie(u, sz_u) = leader_and_size(u, r);
        std::tie(v, sz_v) = leader_and_size(v, r);
        if(u == v) return false;
        if(sz_u < sz_v) {
            std::swap(u, v);
            std::swap(sz_u, sz_v);
        }
        r = par.set(r, u, -(sz_u + sz_v));
        r = par.set(r, v, u);
        root = r;
        return true;
    }
    bool merge(int u, int v) { return merge(u, v, root); }
    Node* get_root() const { return root; }
};
#line 2 "data-structure/persistent/persistent-unionfind.hpp"

#include <algorithm>
#include <tuple>

#line 2 "data-structure/persistent/persistent-array.hpp"

#include <string.h>
#include <utility>
#include <vector>

template <class T, int LOG = 4> struct PersistentArray {
    struct Node {
        T val;
        Node *childs[1 << LOG];

        Node() { memset(childs, 0, sizeof(childs)); }
        Node(const Node *node) { memcpy(childs, node->childs, sizeof(childs)); }
        Node(const Node &node) { memcpy(childs, node.childs, sizeof(childs)); }
    };

    Node *root;
    int depth;
    T identity;
    const int full_bit = (1 << LOG) - 1;

    PersistentArray() {}
    explicit PersistentArray(int N, const T &id = 0)
        : root(new Node()), depth(0), identity(id) {
        PersistentArray(std::vector<T>(N, id));
    }
    PersistentArray(const std::vector<T> &v) : root(new Node()), depth(0) {
        int N = (int)v.size();
        while(N > 0) {
            N >>= LOG;
            depth++;
        }
        N = (int)v.size();
        for(int i = 0; i < N; i++) {
            Node *now = root;
            for(int mask = i, d = depth; d > 0; d--) {
                if(!now->childs[mask & full_bit]) {
                    now->childs[mask & full_bit] = new Node();
                }
                now = now->childs[mask & full_bit];
                mask >>= LOG;
            }
            now->val = v[i];
        }
    }

    T get(int idx) { return get(root, idx); }

    Node *set(int idx, const T &new_value) { return set(root, idx, new_value); }

    T get(Node *node, int idx) {
        for(int i = 0; i < depth; i++) {
            node = node ? node->childs[idx & full_bit] : nullptr;
            idx >>= LOG;
        }
        return (node ? node->val : identity);
    }

    Node *set(Node *node, int idx, T new_value) {
        std::vector<std::pair<Node *, int>> st;
        for(int i = 0; i < depth; i++) {
            st.emplace_back(node, idx & full_bit);
            node = node ? node->childs[idx & full_bit] : nullptr;
            idx >>= LOG;
        }
        Node *new_child = new Node();
        new_child->val = new_value;
        while(!st.empty()) {
            auto [par, k] = st.back();
            st.pop_back();
            Node *new_par = par ? new Node(par) : new Node();
            new_par->childs[k] = new_child;
            new_child = new_par;
        }
        return (root = new_child);
    }
};
#line 7 "data-structure/persistent/persistent-unionfind.hpp"

struct PersistentUnionFind {
    PersistentArray<int> par;
    using Node = decltype(par)::Node;
    Node* root;

    explicit PersistentUnionFind(int n): par(std::vector<int>(n, -1)) {
        root = par.root;
    }
    // (leader, size)
    std::pair<int, int> leader_and_size(int u, Node* r) {
        int p = par.get(r, u);
        return (p < 0 ? std::make_pair(u, -p) : leader_and_size(p, r));
    }
    std::pair<int, int> leader_and_size(int u) {
        return leader_and_size(u, root);
    }
    inline int leader(int u, Node* r) { return leader_and_size(u, r).first; }
    inline int leader(int u) { return leader_and_size(u, root).first; }
    inline int size(int u, Node* r) { return leader_and_size(u, r).second; }
    inline int size(int u) { return leader_and_size(u, root).second; }
    inline bool same(int u, int v, Node* r) { return (leader(u, r) == leader(v, r)); }
    inline bool same(int u, int v) { return same(u, v, root); }
    bool merge(int u, int v, Node* r) {
        int sz_u, sz_v;
        std::tie(u, sz_u) = leader_and_size(u, r);
        std::tie(v, sz_v) = leader_and_size(v, r);
        if(u == v) return false;
        if(sz_u < sz_v) {
            std::swap(u, v);
            std::swap(sz_u, sz_v);
        }
        r = par.set(r, u, -(sz_u + sz_v));
        r = par.set(r, v, u);
        root = r;
        return true;
    }
    bool merge(int u, int v) { return merge(u, v, root); }
    Node* get_root() const { return root; }
};
Back to top page