range_parallel_dsu.hpp¶
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.
Verified by range_parallel_unionfind.
批量合并两个等长区间中对应位置的点；适合大量区间等价约束或字符串片段对应关系。
Implementation¶
#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> &weights) {
build(weights);
}
void build(const std::vector<T> &weights) {
size_ = int(weights.size());
int levels = 1;
while ((1 << levels) <= std::max(1, size_)) {
levels++;
}
parent_.resize(levels);
for (int level = 0; level < levels; level++) {
int length = 1 << level;
int count = std::max(0, size_ - length + 1);
parent_[level].assign(count, -1);
}
component_sum_ = weights;
pair_sum_ = T{};
}
/// @brief Add edges (first+i,second+i) for 0<=i<length and return the new
/// sum of weight products over unordered pairs in the same component.
T unite_ranges(int first, int second, int length) {
assert(length >= 0);
assert(0 <= first && first + length <= size_);
assert(0 <= second && second + length <= size_);
if (length == 0) {
return pair_sum_;
}
int level = 31 - __builtin_clz(unsigned(length));
int block = 1 << level;
unite_blocks(level, first, second);
unite_blocks(level, first + length - block, second + length - block);
return pair_sum_;
}
T pair_sum() const { return pair_sum_; }
bool same(int first, int second) {
assert(0 <= first && first < size_ && 0 <= second && second < size_);
return find(0, first) == find(0, second);
}
private:
int size_ = 0;
std::vector<std::vector<int>> parent_;
std::vector<T> component_sum_;
T pair_sum_{};
int find(int level, int value) {
int root = value;
while (parent_[level][root] >= 0) {
root = parent_[level][root];
}
while (value != root) {
int next = parent_[level][value];
parent_[level][value] = root;
value = next;
}
return root;
}
bool join_roots(int level, int first, int second) {
first = find(level, first);
second = find(level, second);
if (first == second) {
return false;
}
if (parent_[level][first] > parent_[level][second]) {
std::swap(first, second);
}
parent_[level][first] += parent_[level][second];
parent_[level][second] = first;
if (level == 0) {
pair_sum_ += component_sum_[first] * component_sum_[second];
component_sum_[first] += component_sum_[second];
}
return true;
}
void unite_blocks(int level, int first, int second) {
if (!join_roots(level, first, second) || level == 0) {
return;
}
int half = 1 << (level - 1);
unite_blocks(level - 1, first, second);
unite_blocks(level - 1, first + half, second + half);
}
};
} // 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> &weights) {
build(weights);
}
void build(const std::vector<T> &weights) {
size_ = int(weights.size());
int levels = 1;
while ((1 << levels) <= std::max(1, size_)) {
levels++;
}
parent_.resize(levels);
for (int level = 0; level < levels; level++) {
int length = 1 << level;
int count = std::max(0, size_ - length + 1);
parent_[level].assign(count, -1);
}
component_sum_ = weights;
pair_sum_ = T{};
}
/// @brief Add edges (first+i,second+i) for 0<=i<length and return the new
/// sum of weight products over unordered pairs in the same component.
T unite_ranges(int first, int second, int length) {
assert(length >= 0);
assert(0 <= first && first + length <= size_);
assert(0 <= second && second + length <= size_);
if (length == 0) {
return pair_sum_;
}
int level = 31 - __builtin_clz(unsigned(length));
int block = 1 << level;
unite_blocks(level, first, second);
unite_blocks(level, first + length - block, second + length - block);
return pair_sum_;
}
T pair_sum() const { return pair_sum_; }
bool same(int first, int second) {
assert(0 <= first && first < size_ && 0 <= second && second < size_);
return find(0, first) == find(0, second);
}
private:
int size_ = 0;
std::vector<std::vector<int>> parent_;
std::vector<T> component_sum_;
T pair_sum_{};
int find(int level, int value) {
int root = value;
while (parent_[level][root] >= 0) {
root = parent_[level][root];
}
while (value != root) {
int next = parent_[level][value];
parent_[level][value] = root;
value = next;
}
return root;
}
bool join_roots(int level, int first, int second) {
first = find(level, first);
second = find(level, second);
if (first == second) {
return false;
}
if (parent_[level][first] > parent_[level][second]) {
std::swap(first, second);
}
parent_[level][first] += parent_[level][second];
parent_[level][second] = first;
if (level == 0) {
pair_sum_ += component_sum_[first] * component_sum_[second];
component_sum_[first] += component_sum_[second];
}
return true;
}
void unite_blocks(int level, int first, int second) {
if (!join_roots(level, first, second) || level == 0) {
return;
}
int half = 1 << (level - 1);
unite_blocks(level - 1, first, second);
unite_blocks(level - 1, first + half, second + half);
}
};
} // namespace noya