potentialized_group_dsu.hpp¶
在一般群上维护元素间的相对关系；适合位移、仿射变换等不能只用数值差表示的并查集约束。
Complexity: Time: Amortized O(alpha(n)) group operations per query. Space: O(n).
AC 记录：unionfind_with_potential_non_commutative_group。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: Amortized O(alpha(n)) group operations per query.
/// Space: O(n).
#include <cassert>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Weighted union-find over a possibly noncommutative group. Store the
/// relative value parent(x)^-1*x on every parent edge, so path compression
/// multiplies weights from root to leaf in that order. merge(a,b,w) enforces
/// potential(a)^-1*potential(b)=w; reversing a union uses the group inverse,
/// which preserves correctness without assuming commutativity.
template <class T, class Multiply, class Inverse>
class potentialized_group_dsu {
public:
potentialized_group_dsu() = default;
potentialized_group_dsu(int n, T e0, Multiply op, Inverse iv)
: e_(std::move(e0)), mul(std::move(op)), iv0(std::move(iv)) {
build(n);
}
void build(int n) {
assert(n >= 0);
p_.assign(n, -1);
w_.assign(n, e_);
}
int leader(int x) {
assert(0 <= x && x < int(p_.size()));
if (p_[x] < 0) {
return x;
}
int fa = p_[x];
int rt = leader(fa);
w_[x] = mul(w_[fa], w_[x]);
return p_[x] = rt;
}
T potential(int x) {
leader(x);
return w_[x];
}
bool same(int a, int b) { return leader(a) == leader(b); }
int size(int x) { return -p_[leader(x)]; }
std::optional<T> difference(int a, int b) {
T wa = potential(a);
T wb = potential(b);
if (leader(a) != leader(b)) {
return std::nullopt;
}
return mul(iv0(wa), wb);
}
bool merge(int a, int b, const T &dif) {
T wa = potential(a);
T wb = potential(b);
int ra = leader(a);
int rb = leader(b);
if (ra == rb) {
return mul(iv0(wa), wb) == dif;
}
T dw = mul(mul(wa, dif), iv0(wb));
if (-p_[ra] < -p_[rb]) {
std::swap(ra, rb);
dw = iv0(dw);
}
p_[ra] += p_[rb];
p_[rb] = ra;
w_[rb] = std::move(dw);
return true;
}
private:
T e_{};
Multiply mul{};
Inverse iv0{};
std::vector<int> p_;
std::vector<T> w_;
};
} // namespace noya
#ifndef NOYA_POTENTIALIZED_GROUP_DSU_HPP
#define NOYA_POTENTIALIZED_GROUP_DSU_HPP 1
/// @complexity Time: Amortized O(alpha(n)) group operations per query.
/// Space: O(n).
#include <cassert>
#include <optional>
#include <utility>
#include <vector>
namespace noya {
/// @brief Weighted union-find over a possibly noncommutative group. Store the
/// relative value parent(x)^-1*x on every parent edge, so path compression
/// multiplies weights from root to leaf in that order. merge(a,b,w) enforces
/// potential(a)^-1*potential(b)=w; reversing a union uses the group inverse,
/// which preserves correctness without assuming commutativity.
template <class T, class Multiply, class Inverse>
class potentialized_group_dsu {
public:
potentialized_group_dsu() = default;
potentialized_group_dsu(int n, T e0, Multiply op, Inverse iv)
: e_(std::move(e0)), mul(std::move(op)), iv0(std::move(iv)) {
build(n);
}
void build(int n) {
assert(n >= 0);
p_.assign(n, -1);
w_.assign(n, e_);
}
int leader(int x) {
assert(0 <= x && x < int(p_.size()));
if (p_[x] < 0) {
return x;
}
int fa = p_[x];
int rt = leader(fa);
w_[x] = mul(w_[fa], w_[x]);
return p_[x] = rt;
}
T potential(int x) {
leader(x);
return w_[x];
}
bool same(int a, int b) { return leader(a) == leader(b); }
int size(int x) { return -p_[leader(x)]; }
std::optional<T> difference(int a, int b) {
T wa = potential(a);
T wb = potential(b);
if (leader(a) != leader(b)) {
return std::nullopt;
}
return mul(iv0(wa), wb);
}
bool merge(int a, int b, const T &dif) {
T wa = potential(a);
T wb = potential(b);
int ra = leader(a);
int rb = leader(b);
if (ra == rb) {
return mul(iv0(wa), wb) == dif;
}
T dw = mul(mul(wa, dif), iv0(wb));
if (-p_[ra] < -p_[rb]) {
std::swap(ra, rb);
dw = iv0(dw);
}
p_[ra] += p_[rb];
p_[rb] = ra;
w_[rb] = std::move(dw);
return true;
}
private:
T e_{};
Multiply mul{};
Inverse iv0{};
std::vector<int> p_;
std::vector<T> w_;
};
} // namespace noya
#endif // NOYA_POTENTIALIZED_GROUP_DSU_HPP
#include <cassert>
#include <optional>
#include <utility>
#include <vector>
/// @complexity Time: Amortized O(alpha(n)) group operations per query.
/// Space: O(n).
namespace noya {
/// @brief Weighted union-find over a possibly noncommutative group. Store the
/// relative value parent(x)^-1*x on every parent edge, so path compression
/// multiplies weights from root to leaf in that order. merge(a,b,w) enforces
/// potential(a)^-1*potential(b)=w; reversing a union uses the group inverse,
/// which preserves correctness without assuming commutativity.
template <class T, class Multiply, class Inverse>
class potentialized_group_dsu {
public:
potentialized_group_dsu() = default;
potentialized_group_dsu(int n, T e0, Multiply op, Inverse iv)
: e_(std::move(e0)), mul(std::move(op)), iv0(std::move(iv)) {
build(n);
}
void build(int n) {
assert(n >= 0);
p_.assign(n, -1);
w_.assign(n, e_);
}
int leader(int x) {
assert(0 <= x && x < int(p_.size()));
if (p_[x] < 0) {
return x;
}
int fa = p_[x];
int rt = leader(fa);
w_[x] = mul(w_[fa], w_[x]);
return p_[x] = rt;
}
T potential(int x) {
leader(x);
return w_[x];
}
bool same(int a, int b) { return leader(a) == leader(b); }
int size(int x) { return -p_[leader(x)]; }
std::optional<T> difference(int a, int b) {
T wa = potential(a);
T wb = potential(b);
if (leader(a) != leader(b)) {
return std::nullopt;
}
return mul(iv0(wa), wb);
}
bool merge(int a, int b, const T &dif) {
T wa = potential(a);
T wb = potential(b);
int ra = leader(a);
int rb = leader(b);
if (ra == rb) {
return mul(iv0(wa), wb) == dif;
}
T dw = mul(mul(wa, dif), iv0(wb));
if (-p_[ra] < -p_[rb]) {
std::swap(ra, rb);
dw = iv0(dw);
}
p_[ra] += p_[rb];
p_[rb] = ra;
w_[rb] = std::move(dw);
return true;
}
private:
T e_{};
Multiply mul{};
Inverse iv0{};
std::vector<int> p_;
std::vector<T> w_;
};
} // namespace noya