Merge Process Tree
(src/tree/MergeTree.hpp)

View this file on GitHub
Last update: 2024-05-22 00:21:24+09:00
Include: #include "src/tree/MergeTree.hpp"

概要

マージ過程を表す木．

メンバ関数	効果	時間計算量
`MergeTree(n)`	$n$ 要素について初期化する．	$\mathrm{O}(n)$
`build(qs)`	タイプ `0` のクエリでは $2$ 要素 $u, v$ が含まれるグループを併合し，タイプ `1` のクエリではその時点での要素 $u$ の含まれるグループの成す区間 $\lbrack l, r)$ を求めたい．このとき，タイプ `1` のクエリの返り値を求める．	$\mathrm{O}((n + q) \alpha(n))$
`operator[i]`	列の中で頂点 $i$ に対応する位置を返す．	$\mathrm{O}(1)$

出題例

Code

#pragma once
#include <numeric>
#include <tuple>
#include "../atcoder/dsu"

struct MergeTree : atcoder::dsu {
    MergeTree() {}

    MergeTree(int n) : atcoder::dsu(n), n(n), vid(n) {}

    std::vector<std::pair<int, int>> build(const std::vector<std::tuple<int, int, int>>& qs) {
        int q = qs.size();
        std::vector<int> root(n), idx(q, -1);
        std::iota(root.begin(), root.end(), 0);
        child.resize(q);
        range.resize(n + q);
        for (int i = 0; i < q; i++) {
            auto [type, a, b] = qs[i];
            if (type == 0) {
                if (same(a, b)) continue;
                child[i] = {root[leader(a)], root[leader(b)]};
                root[merge(a, b)] = n + i;
            } else
                idx[i] = root[leader(a)];
        }
        int cur = 0;
        for (int i = 0; i < n; i++) {
            if (leader(i) == i) {
                dfs(root[i], cur);
            }
        }
        std::vector<std::pair<int, int>> res(q);
        for (int i = 0; i < q; i++) {
            if (idx[i] != -1) {
                res[i] = range[idx[i]];
            }
        }
        return res;
    }

    int operator[](int v) const { return vid[v]; }

  private:
    int n;
    std::vector<int> vid;
    std::vector<std::pair<int, int>> child, range;

    void dfs(int v, int& cur) {
        int l = cur;
        if (v < n)
            vid[v] = cur++;
        else {
            auto [a, b] = child[v - n];
            dfs(a, cur);
            dfs(b, cur);
        }
        int r = cur;
        range[v] = {l, r};
    }
};

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/dsu.hpp: line -1: no such header

Merge Process Tree (src/tree/MergeTree.hpp)

概要

出題例

Code

Merge Process Tree
(src/tree/MergeTree.hpp)