common_interval_decomposition_tree.hpp¶
给定 0..N-1 的排列，以候选栈和并查集在 O(N α(N)) 时间内构造所有强公共区间的析合树；位置区间和值域均为半开区间，孩子按位置排列。
Complexity: Time: \(O(n \alpha (n))\) amortized. Space: \(O(n)\).
AC 记录：common_interval_decomposition_tree。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n alpha(n)) amortized.
/// Space: O(n).
#include "atcoder/dsu.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
struct common_interval_node {
int l = 0;
int r = 0;
int mn = 0;
int mx = 0;
bool lin = true;
std::vector<int> ch;
};
struct common_interval_tree {
int rt = -1;
std::vector<common_interval_node> tr;
};
/// @brief Build the strong-interval Hasse tree of a permutation.
/// Active adjacent values are joined in a DSU. Candidate left boundaries cache
/// the extrema of their examined suffix. Different components stop the scan:
/// an unseen value separates the suffix values. Once the whole suffix lies in
/// one component, a missing value must occur before its left boundary, so a
/// failed candidate can be discarded permanently. Each candidate is pushed
/// and popped at most once; forest merges build linear or prime nodes.
inline common_interval_tree
common_interval_decomposition_tree(const std::vector<int> &p) {
int n = int(p.size());
assert(n > 0);
struct checkpoint {
int l, mn, mx;
};
std::vector<checkpoint> candidates;
std::vector<int> forest;
std::vector<bool> active(n);
atcoder::dsu components(n);
common_interval_tree res;
res.tr.reserve(2 * n - 1);
auto ins = [&](common_interval_node node) {
res.tr.push_back(std::move(node));
return int(res.tr.size()) - 1;
};
for (int i = 0; i < n; i++) {
int value = p[i];
assert(0 <= value && value < n && !active[value]);
active[value] = true;
if (value > 0 && active[value - 1])
components.merge(value, value - 1);
if (value + 1 < n && active[value + 1])
components.merge(value, value + 1);
int cur = ins({i, i + 1, value, value + 1, true, {}});
int mn = value, mx = value + 1;
while (!forest.empty()) {
int left = -1;
while (!candidates.empty()) {
auto &c = candidates.back();
c.mn = mn = std::min(c.mn, mn);
c.mx = mx = std::max(c.mx, mx);
if (!components.same(p[c.l], value))
break;
if (i + 1 - c.l == mx - mn)
left = c.l;
candidates.pop_back();
if (left != -1)
break;
}
if (left == -1)
break;
int top = forest.back();
auto &a = res.tr[top];
const auto &b = res.tr[cur];
bool extend =
a.lin && !a.ch.empty() &&
((res.tr[a.ch.front()].mn < res.tr[a.ch.back()].mn && a.mx == b.mn) ||
(res.tr[a.ch.front()].mn > res.tr[a.ch.back()].mn && b.mx == a.mn));
if (extend) {
a.ch.push_back(cur);
a.r = i + 1;
a.mn = mn;
a.mx = mx;
cur = top;
forest.pop_back();
} else {
common_interval_node node{left, i + 1, mn, mx, left == a.l, {cur}};
while (!forest.empty() && res.tr[forest.back()].l >= left) {
node.ch.push_back(forest.back());
forest.pop_back();
}
std::reverse(node.ch.begin(), node.ch.end());
cur = ins(std::move(node));
}
}
const auto &node = res.tr[cur];
candidates.push_back({node.l, node.mn, node.mx});
forest.push_back(cur);
}
assert(forest.size() == 1);
res.rt = forest.back();
return res;
}
} // namespace noya
// NOYA_COMMON_INTERVAL_DECOMPOSITION_TREE_HPP
#ifndef NOYA_COMMON_INTERVAL_DECOMPOSITION_TREE_HPP
#define NOYA_COMMON_INTERVAL_DECOMPOSITION_TREE_HPP 1
/// @complexity Time: O(n alpha(n)) amortized.
/// Space: O(n).
#include "atcoder/dsu.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
struct common_interval_node {
int l = 0;
int r = 0;
int mn = 0;
int mx = 0;
bool lin = true;
std::vector<int> ch;
};
struct common_interval_tree {
int rt = -1;
std::vector<common_interval_node> tr;
};
/// @brief Build the strong-interval Hasse tree of a permutation.
/// Active adjacent values are joined in a DSU. Candidate left boundaries cache
/// the extrema of their examined suffix. Different components stop the scan:
/// an unseen value separates the suffix values. Once the whole suffix lies in
/// one component, a missing value must occur before its left boundary, so a
/// failed candidate can be discarded permanently. Each candidate is pushed
/// and popped at most once; forest merges build linear or prime nodes.
inline common_interval_tree
common_interval_decomposition_tree(const std::vector<int> &p) {
int n = int(p.size());
assert(n > 0);
struct checkpoint {
int l, mn, mx;
};
std::vector<checkpoint> candidates;
std::vector<int> forest;
std::vector<bool> active(n);
atcoder::dsu components(n);
common_interval_tree res;
res.tr.reserve(2 * n - 1);
auto ins = [&](common_interval_node node) {
res.tr.push_back(std::move(node));
return int(res.tr.size()) - 1;
};
for (int i = 0; i < n; i++) {
int value = p[i];
assert(0 <= value && value < n && !active[value]);
active[value] = true;
if (value > 0 && active[value - 1])
components.merge(value, value - 1);
if (value + 1 < n && active[value + 1])
components.merge(value, value + 1);
int cur = ins({i, i + 1, value, value + 1, true, {}});
int mn = value, mx = value + 1;
while (!forest.empty()) {
int left = -1;
while (!candidates.empty()) {
auto &c = candidates.back();
c.mn = mn = std::min(c.mn, mn);
c.mx = mx = std::max(c.mx, mx);
if (!components.same(p[c.l], value))
break;
if (i + 1 - c.l == mx - mn)
left = c.l;
candidates.pop_back();
if (left != -1)
break;
}
if (left == -1)
break;
int top = forest.back();
auto &a = res.tr[top];
const auto &b = res.tr[cur];
bool extend =
a.lin && !a.ch.empty() &&
((res.tr[a.ch.front()].mn < res.tr[a.ch.back()].mn && a.mx == b.mn) ||
(res.tr[a.ch.front()].mn > res.tr[a.ch.back()].mn && b.mx == a.mn));
if (extend) {
a.ch.push_back(cur);
a.r = i + 1;
a.mn = mn;
a.mx = mx;
cur = top;
forest.pop_back();
} else {
common_interval_node node{left, i + 1, mn, mx, left == a.l, {cur}};
while (!forest.empty() && res.tr[forest.back()].l >= left) {
node.ch.push_back(forest.back());
forest.pop_back();
}
std::reverse(node.ch.begin(), node.ch.end());
cur = ins(std::move(node));
}
}
const auto &node = res.tr[cur];
candidates.push_back({node.l, node.mn, node.mx});
forest.push_back(cur);
}
assert(forest.size() == 1);
res.rt = forest.back();
return res;
}
} // namespace noya
#endif // NOYA_COMMON_INTERVAL_DECOMPOSITION_TREE_HPP
/// @complexity Time: O(n alpha(n)) amortized.
/// Space: O(n).
#include <algorithm>
#include <cassert>
#include <vector>
namespace atcoder {
// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
public:
dsu() : _n(0) {}
explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
return _leader(a);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
int _leader(int a) {
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = _leader(parent_or_size[a]);
}
};
} // namespace atcoder
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
namespace noya {
struct common_interval_node {
int l = 0;
int r = 0;
int mn = 0;
int mx = 0;
bool lin = true;
std::vector<int> ch;
};
struct common_interval_tree {
int rt = -1;
std::vector<common_interval_node> tr;
};
/// @brief Build the strong-interval Hasse tree of a permutation.
/// Active adjacent values are joined in a DSU. Candidate left boundaries cache
/// the extrema of their examined suffix. Different components stop the scan:
/// an unseen value separates the suffix values. Once the whole suffix lies in
/// one component, a missing value must occur before its left boundary, so a
/// failed candidate can be discarded permanently. Each candidate is pushed
/// and popped at most once; forest merges build linear or prime nodes.
inline common_interval_tree
common_interval_decomposition_tree(const std::vector<int> &p) {
int n = int(p.size());
assert(n > 0);
struct checkpoint {
int l, mn, mx;
};
std::vector<checkpoint> candidates;
std::vector<int> forest;
std::vector<bool> active(n);
atcoder::dsu components(n);
common_interval_tree res;
res.tr.reserve(2 * n - 1);
auto ins = [&](common_interval_node node) {
res.tr.push_back(std::move(node));
return int(res.tr.size()) - 1;
};
for (int i = 0; i < n; i++) {
int value = p[i];
assert(0 <= value && value < n && !active[value]);
active[value] = true;
if (value > 0 && active[value - 1])
components.merge(value, value - 1);
if (value + 1 < n && active[value + 1])
components.merge(value, value + 1);
int cur = ins({i, i + 1, value, value + 1, true, {}});
int mn = value, mx = value + 1;
while (!forest.empty()) {
int left = -1;
while (!candidates.empty()) {
auto &c = candidates.back();
c.mn = mn = std::min(c.mn, mn);
c.mx = mx = std::max(c.mx, mx);
if (!components.same(p[c.l], value))
break;
if (i + 1 - c.l == mx - mn)
left = c.l;
candidates.pop_back();
if (left != -1)
break;
}
if (left == -1)
break;
int top = forest.back();
auto &a = res.tr[top];
const auto &b = res.tr[cur];
bool extend =
a.lin && !a.ch.empty() &&
((res.tr[a.ch.front()].mn < res.tr[a.ch.back()].mn && a.mx == b.mn) ||
(res.tr[a.ch.front()].mn > res.tr[a.ch.back()].mn && b.mx == a.mn));
if (extend) {
a.ch.push_back(cur);
a.r = i + 1;
a.mn = mn;
a.mx = mx;
cur = top;
forest.pop_back();
} else {
common_interval_node node{left, i + 1, mn, mx, left == a.l, {cur}};
while (!forest.empty() && res.tr[forest.back()].l >= left) {
node.ch.push_back(forest.back());
forest.pop_back();
}
std::reverse(node.ch.begin(), node.ch.end());
cur = ins(std::move(node));
}
}
const auto &node = res.tr[cur];
candidates.push_back({node.l, node.mn, node.mx});
forest.push_back(cur);
}
assert(forest.size() == 1);
res.rt = forest.back();
return res;
}
} // namespace noya
// NOYA_COMMON_INTERVAL_DECOMPOSITION_TREE_HPP