range_parallel_dsu.hpp¶
批量合并两个等长区间中对应位置的点；适合大量区间等价约束或字符串片段对应关系。
Complexity: Time: O((n + q) log n alpha(n)) total for q range unions. Space: O(n log n).
AC 记录：range_parallel_unionfind。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O((n + q) log n alpha(n)) total for q range unions.
/// Space: O(n log n).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
/// @brief Add all equal-offset edges between two ranges and maintain a
/// component-pair aggregate. Level h represents intervals of length 2^h.
/// Merging two level-h classes recursively merges their left and right halves;
/// since each class pair succeeds only once, all downward propagation is
/// amortized over O(n log n) interval nodes. Any length is covered by its first
/// and last largest-power-of-two blocks.
template <class T> class range_parallel_dsu {
public:
range_parallel_dsu() = default;
explicit range_parallel_dsu(const std::vector<T> &w) {
build(w);
}
void build(const std::vector<T> &w) {
n = int(w.size());
int lg = 1;
while ((1 << lg) <= std::max(1, n)) {
lg++;
}
fa.resize(lg);
for (int dep = 0; dep < lg; dep++) {
int len = 1 << dep;
int cnt = std::max(0, n - len + 1);
fa[dep].assign(cnt, -1);
}
s = w;
ans = T{};
}
/// @brief Add edges (a+i,b+i) for 0<=i<len and return the new
/// sum of weight products over unordered pairs in the same component.
T unite_ranges(int a, int b, int len) {
assert(len >= 0);
assert(0 <= a && a + len <= n);
assert(0 <= b && b + len <= n);
if (len == 0) {
return ans;
}
int dep = 31 - __builtin_clz(unsigned(len));
int blk = 1 << dep;
unite_blocks(dep, a, b);
unite_blocks(dep, a + len - blk, b + len - blk);
return ans;
}
T pair_sum() const { return ans; }
bool same(int a, int b) {
assert(0 <= a && a < n && 0 <= b && b < n);
return find(0, a) == find(0, b);
}
private:
int n = 0;
std::vector<std::vector<int>> fa;
std::vector<T> s;
T ans{};
int find(int dep, int val) {
int rt = val;
while (fa[dep][rt] >= 0) {
rt = fa[dep][rt];
}
while (val != rt) {
int nxt = fa[dep][val];
fa[dep][val] = rt;
val = nxt;
}
return rt;
}
bool join_roots(int dep, int a, int b) {
a = find(dep, a);
b = find(dep, b);
if (a == b) {
return false;
}
if (fa[dep][a] > fa[dep][b]) {
std::swap(a, b);
}
fa[dep][a] += fa[dep][b];
fa[dep][b] = a;
if (dep == 0) {
ans += s[a] * s[b];
s[a] += s[b];
}
return true;
}
void unite_blocks(int dep, int a, int b) {
if (!join_roots(dep, a, b) || dep == 0) {
return;
}
int hf = 1 << (dep - 1);
unite_blocks(dep - 1, a, b);
unite_blocks(dep - 1, a + hf, b + hf);
}
};
} // namespace noya
#ifndef NOYA_RANGE_PARALLEL_DSU_HPP
#define NOYA_RANGE_PARALLEL_DSU_HPP 1
/// @complexity Time: O((n + q) log n alpha(n)) total for q range unions.
/// Space: O(n log n).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
namespace noya {
/// @brief Add all equal-offset edges between two ranges and maintain a
/// component-pair aggregate. Level h represents intervals of length 2^h.
/// Merging two level-h classes recursively merges their left and right halves;
/// since each class pair succeeds only once, all downward propagation is
/// amortized over O(n log n) interval nodes. Any length is covered by its first
/// and last largest-power-of-two blocks.
template <class T> class range_parallel_dsu {
public:
range_parallel_dsu() = default;
explicit range_parallel_dsu(const std::vector<T> &w) {
build(w);
}
void build(const std::vector<T> &w) {
n = int(w.size());
int lg = 1;
while ((1 << lg) <= std::max(1, n)) {
lg++;
}
fa.resize(lg);
for (int dep = 0; dep < lg; dep++) {
int len = 1 << dep;
int cnt = std::max(0, n - len + 1);
fa[dep].assign(cnt, -1);
}
s = w;
ans = T{};
}
/// @brief Add edges (a+i,b+i) for 0<=i<len and return the new
/// sum of weight products over unordered pairs in the same component.
T unite_ranges(int a, int b, int len) {
assert(len >= 0);
assert(0 <= a && a + len <= n);
assert(0 <= b && b + len <= n);
if (len == 0) {
return ans;
}
int dep = 31 - __builtin_clz(unsigned(len));
int blk = 1 << dep;
unite_blocks(dep, a, b);
unite_blocks(dep, a + len - blk, b + len - blk);
return ans;
}
T pair_sum() const { return ans; }
bool same(int a, int b) {
assert(0 <= a && a < n && 0 <= b && b < n);
return find(0, a) == find(0, b);
}
private:
int n = 0;
std::vector<std::vector<int>> fa;
std::vector<T> s;
T ans{};
int find(int dep, int val) {
int rt = val;
while (fa[dep][rt] >= 0) {
rt = fa[dep][rt];
}
while (val != rt) {
int nxt = fa[dep][val];
fa[dep][val] = rt;
val = nxt;
}
return rt;
}
bool join_roots(int dep, int a, int b) {
a = find(dep, a);
b = find(dep, b);
if (a == b) {
return false;
}
if (fa[dep][a] > fa[dep][b]) {
std::swap(a, b);
}
fa[dep][a] += fa[dep][b];
fa[dep][b] = a;
if (dep == 0) {
ans += s[a] * s[b];
s[a] += s[b];
}
return true;
}
void unite_blocks(int dep, int a, int b) {
if (!join_roots(dep, a, b) || dep == 0) {
return;
}
int hf = 1 << (dep - 1);
unite_blocks(dep - 1, a, b);
unite_blocks(dep - 1, a + hf, b + hf);
}
};
} // namespace noya
#endif // NOYA_RANGE_PARALLEL_DSU_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <utility>
#include <vector>
/// @complexity Time: O((n + q) log n alpha(n)) total for q range unions.
/// Space: O(n log n).
namespace noya {
/// @brief Add all equal-offset edges between two ranges and maintain a
/// component-pair aggregate. Level h represents intervals of length 2^h.
/// Merging two level-h classes recursively merges their left and right halves;
/// since each class pair succeeds only once, all downward propagation is
/// amortized over O(n log n) interval nodes. Any length is covered by its first
/// and last largest-power-of-two blocks.
template <class T> class range_parallel_dsu {
public:
range_parallel_dsu() = default;
explicit range_parallel_dsu(const std::vector<T> &w) {
build(w);
}
void build(const std::vector<T> &w) {
n = int(w.size());
int lg = 1;
while ((1 << lg) <= std::max(1, n)) {
lg++;
}
fa.resize(lg);
for (int dep = 0; dep < lg; dep++) {
int len = 1 << dep;
int cnt = std::max(0, n - len + 1);
fa[dep].assign(cnt, -1);
}
s = w;
ans = T{};
}
/// @brief Add edges (a+i,b+i) for 0<=i<len and return the new
/// sum of weight products over unordered pairs in the same component.
T unite_ranges(int a, int b, int len) {
assert(len >= 0);
assert(0 <= a && a + len <= n);
assert(0 <= b && b + len <= n);
if (len == 0) {
return ans;
}
int dep = 31 - __builtin_clz(unsigned(len));
int blk = 1 << dep;
unite_blocks(dep, a, b);
unite_blocks(dep, a + len - blk, b + len - blk);
return ans;
}
T pair_sum() const { return ans; }
bool same(int a, int b) {
assert(0 <= a && a < n && 0 <= b && b < n);
return find(0, a) == find(0, b);
}
private:
int n = 0;
std::vector<std::vector<int>> fa;
std::vector<T> s;
T ans{};
int find(int dep, int val) {
int rt = val;
while (fa[dep][rt] >= 0) {
rt = fa[dep][rt];
}
while (val != rt) {
int nxt = fa[dep][val];
fa[dep][val] = rt;
val = nxt;
}
return rt;
}
bool join_roots(int dep, int a, int b) {
a = find(dep, a);
b = find(dep, b);
if (a == b) {
return false;
}
if (fa[dep][a] > fa[dep][b]) {
std::swap(a, b);
}
fa[dep][a] += fa[dep][b];
fa[dep][b] = a;
if (dep == 0) {
ans += s[a] * s[b];
s[a] += s[b];
}
return true;
}
void unite_blocks(int dep, int a, int b) {
if (!join_roots(dep, a, b) || dep == 0) {
return;
}
int hf = 1 << (dep - 1);
unite_blocks(dep - 1, a, b);
unite_blocks(dep - 1, a + hf, b + hf);
}
};
} // namespace noya