persistent_dsu.hpp¶
查询并查集在任意历史版本中的连通关系，并从旧版本继续合并；适合版本树上的动态连通性。
Complexity: Time: O(log^2 n) per leader, same, size, or merge query. Space: O(log n) new nodes per successful merge and O(1) per version copy.
AC 记录：persistent_unionfind。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(log^2 n) per leader, same, size, or merge query.
/// Space: O(log n) new nodes per successful merge and O(1) per version copy.
#include <cassert>
#include <memory>
#include <utility>
#include <vector>
namespace noya {
/// @brief Fully persistent union-find. Union by size keeps every parent chain
/// logarithmic, while a path-copying segment tree stores the parent-or-size
/// array. Versions share all untouched segment-tree nodes, so any old version
/// can be queried or branched from after later merges.
class persistent_dsu {
struct node {
int ls = 0;
int rs = 0;
int val = -1;
};
struct storage {
std::vector<node> tr{{}};
int get(int rt, int low, int hi, int pos) const {
if (rt == 0) {
return -1;
}
if (hi - low == 1) {
return tr[rt].val;
}
int mid = low + (hi - low) / 2;
if (pos < mid) {
return get(tr[rt].ls, low, mid, pos);
}
return get(tr[rt].rs, mid, hi, pos);
}
int set(int rt, int low, int hi, int pos, int val) {
int cur = int(tr.size());
tr.push_back(tr[rt]);
if (hi - low == 1) {
tr[cur].val = val;
return cur;
}
int mid = low + (hi - low) / 2;
if (pos < mid) {
tr[cur].ls = set(tr[rt].ls, low, mid, pos, val);
} else {
tr[cur].rs = set(tr[rt].rs, mid, hi, pos, val);
}
return cur;
}
};
int n = 0;
int rt0 = 0;
std::shared_ptr<storage> dat;
persistent_dsu(int cnt, int rt, std::shared_ptr<storage> da0)
: n(cnt), rt0(rt), dat(std::move(da0)) {}
int value(int pos) const {
assert(dat && 0 <= pos && pos < n);
return dat->get(rt0, 0, n, pos);
}
public:
persistent_dsu() = default;
explicit persistent_dsu(int cnt) : n(cnt), dat(std::make_shared<storage>()) {
assert(cnt > 0);
}
/// @brief Return the representative of vertex in this version.
int leader(int u) const {
int fa = value(u);
while (fa >= 0) {
u = fa;
fa = value(u);
}
return u;
}
bool same(int a, int b) const { return leader(a) == leader(b); }
int size(int u) const { return -value(leader(u)); }
/// @brief Return a new version in which the two components are united.
persistent_dsu merge(int a, int b) const {
a = leader(a);
b = leader(b);
if (a == b) {
return *this;
}
int sz1 = -value(a);
int sz2 = -value(b);
if (sz1 < sz2) {
std::swap(a, b);
std::swap(sz1, sz2);
}
int nr = dat->set(rt0, 0, n, a, -(sz1 + sz2));
nr = dat->set(nr, 0, n, b, a);
return persistent_dsu(n, nr, dat);
}
};
} // namespace noya
#ifndef NOYA_PERSISTENT_DSU_HPP
#define NOYA_PERSISTENT_DSU_HPP 1
/// @complexity Time: O(log^2 n) per leader, same, size, or merge query.
/// Space: O(log n) new nodes per successful merge and O(1) per version copy.
#include <cassert>
#include <memory>
#include <utility>
#include <vector>
namespace noya {
/// @brief Fully persistent union-find. Union by size keeps every parent chain
/// logarithmic, while a path-copying segment tree stores the parent-or-size
/// array. Versions share all untouched segment-tree nodes, so any old version
/// can be queried or branched from after later merges.
class persistent_dsu {
struct node {
int ls = 0;
int rs = 0;
int val = -1;
};
struct storage {
std::vector<node> tr{{}};
int get(int rt, int low, int hi, int pos) const {
if (rt == 0) {
return -1;
}
if (hi - low == 1) {
return tr[rt].val;
}
int mid = low + (hi - low) / 2;
if (pos < mid) {
return get(tr[rt].ls, low, mid, pos);
}
return get(tr[rt].rs, mid, hi, pos);
}
int set(int rt, int low, int hi, int pos, int val) {
int cur = int(tr.size());
tr.push_back(tr[rt]);
if (hi - low == 1) {
tr[cur].val = val;
return cur;
}
int mid = low + (hi - low) / 2;
if (pos < mid) {
tr[cur].ls = set(tr[rt].ls, low, mid, pos, val);
} else {
tr[cur].rs = set(tr[rt].rs, mid, hi, pos, val);
}
return cur;
}
};
int n = 0;
int rt0 = 0;
std::shared_ptr<storage> dat;
persistent_dsu(int cnt, int rt, std::shared_ptr<storage> da0)
: n(cnt), rt0(rt), dat(std::move(da0)) {}
int value(int pos) const {
assert(dat && 0 <= pos && pos < n);
return dat->get(rt0, 0, n, pos);
}
public:
persistent_dsu() = default;
explicit persistent_dsu(int cnt) : n(cnt), dat(std::make_shared<storage>()) {
assert(cnt > 0);
}
/// @brief Return the representative of vertex in this version.
int leader(int u) const {
int fa = value(u);
while (fa >= 0) {
u = fa;
fa = value(u);
}
return u;
}
bool same(int a, int b) const { return leader(a) == leader(b); }
int size(int u) const { return -value(leader(u)); }
/// @brief Return a new version in which the two components are united.
persistent_dsu merge(int a, int b) const {
a = leader(a);
b = leader(b);
if (a == b) {
return *this;
}
int sz1 = -value(a);
int sz2 = -value(b);
if (sz1 < sz2) {
std::swap(a, b);
std::swap(sz1, sz2);
}
int nr = dat->set(rt0, 0, n, a, -(sz1 + sz2));
nr = dat->set(nr, 0, n, b, a);
return persistent_dsu(n, nr, dat);
}
};
} // namespace noya
#endif // NOYA_PERSISTENT_DSU_HPP
#include <cassert>
#include <memory>
#include <utility>
#include <vector>
/// @complexity Time: O(log^2 n) per leader, same, size, or merge query.
/// Space: O(log n) new nodes per successful merge and O(1) per version copy.
namespace noya {
/// @brief Fully persistent union-find. Union by size keeps every parent chain
/// logarithmic, while a path-copying segment tree stores the parent-or-size
/// array. Versions share all untouched segment-tree nodes, so any old version
/// can be queried or branched from after later merges.
class persistent_dsu {
struct node {
int ls = 0;
int rs = 0;
int val = -1;
};
struct storage {
std::vector<node> tr{{}};
int get(int rt, int low, int hi, int pos) const {
if (rt == 0) {
return -1;
}
if (hi - low == 1) {
return tr[rt].val;
}
int mid = low + (hi - low) / 2;
if (pos < mid) {
return get(tr[rt].ls, low, mid, pos);
}
return get(tr[rt].rs, mid, hi, pos);
}
int set(int rt, int low, int hi, int pos, int val) {
int cur = int(tr.size());
tr.push_back(tr[rt]);
if (hi - low == 1) {
tr[cur].val = val;
return cur;
}
int mid = low + (hi - low) / 2;
if (pos < mid) {
tr[cur].ls = set(tr[rt].ls, low, mid, pos, val);
} else {
tr[cur].rs = set(tr[rt].rs, mid, hi, pos, val);
}
return cur;
}
};
int n = 0;
int rt0 = 0;
std::shared_ptr<storage> dat;
persistent_dsu(int cnt, int rt, std::shared_ptr<storage> da0)
: n(cnt), rt0(rt), dat(std::move(da0)) {}
int value(int pos) const {
assert(dat && 0 <= pos && pos < n);
return dat->get(rt0, 0, n, pos);
}
public:
persistent_dsu() = default;
explicit persistent_dsu(int cnt) : n(cnt), dat(std::make_shared<storage>()) {
assert(cnt > 0);
}
/// @brief Return the representative of vertex in this version.
int leader(int u) const {
int fa = value(u);
while (fa >= 0) {
u = fa;
fa = value(u);
}
return u;
}
bool same(int a, int b) const { return leader(a) == leader(b); }
int size(int u) const { return -value(leader(u)); }
/// @brief Return a new version in which the two components are united.
persistent_dsu merge(int a, int b) const {
a = leader(a);
b = leader(b);
if (a == b) {
return *this;
}
int sz1 = -value(a);
int sz2 = -value(b);
if (sz1 < sz2) {
std::swap(a, b);
std::swap(sz1, sz2);
}
int nr = dat->set(rt0, 0, n, a, -(sz1 + sz2));
nr = dat->set(nr, 0, n, b, a);
return persistent_dsu(n, nr, dat);
}
};
} // namespace noya