common_interval_decomposition_tree.hpp¶
Build the strong-interval Hasse tree of a permutation. For every possible left endpoint, a lazy segment tree maintains max-min-length+1 for the suffix ending at the current position. Monotone min/max stacks update this value on exactly the ranges whose extrema change, so value zero detects a new common interval. A second stack merges adjacent value ranges into linear nodes; otherwise all nodes up to the detected boundary form one prime node. Every merge is permanent, giving a laminar tree containing exactly the strong intervals.
Verified by common_interval_decomposition_tree.
构造两个排列的公共区间分解树；用于统计或枚举在两个排列中都连续出现的元素集合。
Implementation¶
#ifndef NOYA_COMMON_INTERVAL_DECOMPOSITION_TREE_HPP
#define NOYA_COMMON_INTERVAL_DECOMPOSITION_TREE_HPP 1
/// @complexity Time: O(n log n).
/// Space: O(n).
#include "noya/lazy_segtree.hpp"
#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>
namespace noya {
struct common_interval_node {
int left = 0;
int right = 0;
int minimum = 0;
int maximum = 0;
bool linear = true;
std::vector<int> children;
};
struct common_interval_tree {
int root = -1;
std::vector<common_interval_node> nodes;
};
namespace common_interval_internal {
struct maximum_monoid {
using value_type = int;
static value_type unit() { return std::numeric_limits<int>::lowest() / 4; }
static value_type op(value_type first, value_type second) {
return std::max(first, second);
}
};
struct addition_action {
using value_type = int;
static value_type unit() { return 0; }
static value_type composition(value_type newer, value_type older) {
return newer + older;
}
static int apply(value_type addition, int value) { return value + addition; }
};
} // namespace common_interval_internal
/// @brief Build the strong-interval Hasse tree of a permutation.
/// For every possible left endpoint, a lazy segment tree maintains
/// `max-min-length+1` for the suffix ending at the current position. Monotone
/// min/max stacks update this value on exactly the ranges whose extrema
/// change, so value zero detects a new common interval. A second stack merges
/// adjacent value ranges into linear nodes; otherwise all nodes up to the
/// detected boundary form one prime node. Every merge is permanent, giving a
/// laminar tree containing exactly the strong intervals.
inline common_interval_tree
common_interval_decomposition_tree(const std::vector<int> &permutation) {
int size = int(permutation.size());
assert(size > 0);
std::vector<bool> seen(size);
for (int value : permutation) {
assert(0 <= value && value < size);
assert(!seen[value]);
seen[value] = true;
}
using segment_tree =
lazy_segtree<common_interval_internal::maximum_monoid,
common_interval_internal::addition_action>;
segment_tree differences(size);
std::vector<int> minimum_stack;
std::vector<int> maximum_stack;
std::vector<int> node_stack;
common_interval_tree result;
result.nodes.reserve(size * 2 - 1);
auto add_node = [&](common_interval_node node) {
result.nodes.push_back(std::move(node));
return int(result.nodes.size()) - 1;
};
auto adjacent_values = [&](int first, int second) {
return result.nodes[first].minimum == result.nodes[second].maximum ||
result.nodes[first].maximum == result.nodes[second].minimum;
};
for (int index = 0; index < size; index++) {
int right = index;
while (!minimum_stack.empty() &&
permutation[minimum_stack.back()] > permutation[index]) {
minimum_stack.pop_back();
int left = minimum_stack.empty() ? 0 : minimum_stack.back() + 1;
differences.apply(left, right,
permutation[index] - permutation[right - 1]);
right = left;
}
minimum_stack.push_back(index);
right = index;
while (!maximum_stack.empty() &&
permutation[maximum_stack.back()] < permutation[index]) {
maximum_stack.pop_back();
int left = maximum_stack.empty() ? 0 : maximum_stack.back() + 1;
differences.apply(left, right,
-permutation[index] + permutation[right - 1]);
right = left;
}
maximum_stack.push_back(index);
differences.apply(0, index, 1);
int current = add_node(common_interval_node{
index, index + 1, permutation[index], permutation[index] + 1, true,
{}});
while (true) {
if (!node_stack.empty()) {
int top = node_stack.back();
if (result.nodes[top].linear &&
!result.nodes[top].children.empty() &&
adjacent_values(current, result.nodes[top].children.back())) {
node_stack.pop_back();
result.nodes[top].children.push_back(current);
result.nodes[top].left = std::min(result.nodes[top].left,
result.nodes[current].left);
result.nodes[top].right = std::max(result.nodes[top].right,
result.nodes[current].right);
result.nodes[top].minimum = std::min(result.nodes[top].minimum,
result.nodes[current].minimum);
result.nodes[top].maximum = std::max(result.nodes[top].maximum,
result.nodes[current].maximum);
current = top;
continue;
}
if (adjacent_values(top, current)) {
node_stack.pop_back();
common_interval_node joined;
joined.left = result.nodes[top].left;
joined.right = result.nodes[current].right;
joined.minimum = std::min(result.nodes[top].minimum,
result.nodes[current].minimum);
joined.maximum = std::max(result.nodes[top].maximum,
result.nodes[current].maximum);
joined.linear = true;
joined.children = {top, current};
current = add_node(std::move(joined));
continue;
}
}
node_stack.push_back(current);
if (node_stack.size() == 1) {
break;
}
int left = result.nodes[node_stack.back()].left;
if (differences.prod(0, left) != 0) {
break;
}
int top = node_stack.back();
node_stack.pop_back();
common_interval_node prime = result.nodes[top];
prime.linear = false;
prime.children = {top};
current = add_node(std::move(prime));
do {
assert(!node_stack.empty());
top = node_stack.back();
node_stack.pop_back();
result.nodes[current].children.push_back(top);
result.nodes[current].left =
std::min(result.nodes[current].left, result.nodes[top].left);
result.nodes[current].right =
std::max(result.nodes[current].right, result.nodes[top].right);
result.nodes[current].minimum =
std::min(result.nodes[current].minimum, result.nodes[top].minimum);
result.nodes[current].maximum =
std::max(result.nodes[current].maximum, result.nodes[top].maximum);
} while (result.nodes[current].right - result.nodes[current].left !=
result.nodes[current].maximum - result.nodes[current].minimum);
std::reverse(result.nodes[current].children.begin(),
result.nodes[current].children.end());
}
differences.set(index, 0);
}
assert(node_stack.size() == 1);
result.root = node_stack.back();
return result;
}
} // namespace noya
#endif // NOYA_COMMON_INTERVAL_DECOMPOSITION_TREE_HPP
#include <algorithm>
#include <cassert>
#include <limits>
#include <vector>
/// @complexity Time: O(n log n).
/// Space: O(n).
/// @complexity Time: O(n) build and O(log n) point/range operation.
/// Space: O(n).
namespace noya {
/// @brief Lazy segment tree for a monoid acted on by a mapping monoid.
/// Monoid provides `value_type`, `unit()`, and `op(left, right)`.
/// Action provides `value_type`, `unit()`, `composition(newer, older)`, and
/// `apply(action, monoid_value)`.
template <class Monoid, class Action> struct lazy_segtree {
using S = typename Monoid::value_type;
using F = typename Action::value_type;
int n = 0;
int size = 1;
int log = 0;
std::vector<S> data;
std::vector<F> lazy;
lazy_segtree() = default;
explicit lazy_segtree(int n_) { build(n_); }
explicit lazy_segtree(const std::vector<S> &values) { build(values); }
void build(int n_) { build(std::vector<S>(n_, Monoid::unit())); }
void build(const std::vector<S> &values) {
n = int(values.size());
size = 1;
log = 0;
while (size < n) {
size <<= 1;
log++;
}
data.assign(size << 1, Monoid::unit());
lazy.assign(size, Action::unit());
for (int i = 0; i < n; i++) {
data[size + i] = values[i];
}
for (int node = size - 1; node >= 1; node--) {
pull(node);
}
}
void set(int position, const S &value) {
assert(0 <= position && position < n);
position += size;
for (int height = log; height >= 1; height--) {
push(position >> height);
}
data[position] = value;
for (int height = 1; height <= log; height++) {
pull(position >> height);
}
}
S get(int position) {
assert(0 <= position && position < n);
position += size;
for (int height = log; height >= 1; height--) {
push(position >> height);
}
return data[position];
}
S prod(int left, int right) {
assert(0 <= left && left <= right && right <= n);
if (left == right) {
return Monoid::unit();
}
left += size;
right += size;
for (int height = log; height >= 1; height--) {
if (((left >> height) << height) != left) {
push(left >> height);
}
if (((right >> height) << height) != right) {
push((right - 1) >> height);
}
}
S first = Monoid::unit();
S second = Monoid::unit();
while (left < right) {
if (left & 1) {
first = Monoid::op(first, data[left++]);
}
if (right & 1) {
second = Monoid::op(data[--right], second);
}
left >>= 1;
right >>= 1;
}
return Monoid::op(first, second);
}
S all_prod() const { return data[1]; }
/// @brief Apply an action to every element in [left, right).
void apply(int left, int right, const F &action) {
assert(0 <= left && left <= right && right <= n);
if (left == right) {
return;
}
left += size;
right += size;
for (int height = log; height >= 1; height--) {
if (((left >> height) << height) != left) {
push(left >> height);
}
if (((right >> height) << height) != right) {
push((right - 1) >> height);
}
}
int original_left = left;
int original_right = right;
while (left < right) {
if (left & 1) {
all_apply(left++, action);
}
if (right & 1) {
all_apply(--right, action);
}
left >>= 1;
right >>= 1;
}
left = original_left;
right = original_right;
for (int height = 1; height <= log; height++) {
if (((left >> height) << height) != left) {
pull(left >> height);
}
if (((right >> height) << height) != right) {
pull((right - 1) >> height);
}
}
}
private:
void pull(int node) {
data[node] = Monoid::op(data[node << 1], data[node << 1 | 1]);
}
void all_apply(int node, const F &action) {
data[node] = Action::apply(action, data[node]);
if (node < size) {
lazy[node] = Action::composition(action, lazy[node]);
}
}
void push(int node) {
all_apply(node << 1, lazy[node]);
all_apply(node << 1 | 1, lazy[node]);
lazy[node] = Action::unit();
}
};
} // namespace noya
namespace noya {
struct common_interval_node {
int left = 0;
int right = 0;
int minimum = 0;
int maximum = 0;
bool linear = true;
std::vector<int> children;
};
struct common_interval_tree {
int root = -1;
std::vector<common_interval_node> nodes;
};
namespace common_interval_internal {
struct maximum_monoid {
using value_type = int;
static value_type unit() { return std::numeric_limits<int>::lowest() / 4; }
static value_type op(value_type first, value_type second) {
return std::max(first, second);
}
};
struct addition_action {
using value_type = int;
static value_type unit() { return 0; }
static value_type composition(value_type newer, value_type older) {
return newer + older;
}
static int apply(value_type addition, int value) { return value + addition; }
};
} // namespace common_interval_internal
/// @brief Build the strong-interval Hasse tree of a permutation.
/// For every possible left endpoint, a lazy segment tree maintains
/// `max-min-length+1` for the suffix ending at the current position. Monotone
/// min/max stacks update this value on exactly the ranges whose extrema
/// change, so value zero detects a new common interval. A second stack merges
/// adjacent value ranges into linear nodes; otherwise all nodes up to the
/// detected boundary form one prime node. Every merge is permanent, giving a
/// laminar tree containing exactly the strong intervals.
inline common_interval_tree
common_interval_decomposition_tree(const std::vector<int> &permutation) {
int size = int(permutation.size());
assert(size > 0);
std::vector<bool> seen(size);
for (int value : permutation) {
assert(0 <= value && value < size);
assert(!seen[value]);
seen[value] = true;
}
using segment_tree =
lazy_segtree<common_interval_internal::maximum_monoid,
common_interval_internal::addition_action>;
segment_tree differences(size);
std::vector<int> minimum_stack;
std::vector<int> maximum_stack;
std::vector<int> node_stack;
common_interval_tree result;
result.nodes.reserve(size * 2 - 1);
auto add_node = [&](common_interval_node node) {
result.nodes.push_back(std::move(node));
return int(result.nodes.size()) - 1;
};
auto adjacent_values = [&](int first, int second) {
return result.nodes[first].minimum == result.nodes[second].maximum ||
result.nodes[first].maximum == result.nodes[second].minimum;
};
for (int index = 0; index < size; index++) {
int right = index;
while (!minimum_stack.empty() &&
permutation[minimum_stack.back()] > permutation[index]) {
minimum_stack.pop_back();
int left = minimum_stack.empty() ? 0 : minimum_stack.back() + 1;
differences.apply(left, right,
permutation[index] - permutation[right - 1]);
right = left;
}
minimum_stack.push_back(index);
right = index;
while (!maximum_stack.empty() &&
permutation[maximum_stack.back()] < permutation[index]) {
maximum_stack.pop_back();
int left = maximum_stack.empty() ? 0 : maximum_stack.back() + 1;
differences.apply(left, right,
-permutation[index] + permutation[right - 1]);
right = left;
}
maximum_stack.push_back(index);
differences.apply(0, index, 1);
int current = add_node(common_interval_node{
index, index + 1, permutation[index], permutation[index] + 1, true,
{}});
while (true) {
if (!node_stack.empty()) {
int top = node_stack.back();
if (result.nodes[top].linear &&
!result.nodes[top].children.empty() &&
adjacent_values(current, result.nodes[top].children.back())) {
node_stack.pop_back();
result.nodes[top].children.push_back(current);
result.nodes[top].left = std::min(result.nodes[top].left,
result.nodes[current].left);
result.nodes[top].right = std::max(result.nodes[top].right,
result.nodes[current].right);
result.nodes[top].minimum = std::min(result.nodes[top].minimum,
result.nodes[current].minimum);
result.nodes[top].maximum = std::max(result.nodes[top].maximum,
result.nodes[current].maximum);
current = top;
continue;
}
if (adjacent_values(top, current)) {
node_stack.pop_back();
common_interval_node joined;
joined.left = result.nodes[top].left;
joined.right = result.nodes[current].right;
joined.minimum = std::min(result.nodes[top].minimum,
result.nodes[current].minimum);
joined.maximum = std::max(result.nodes[top].maximum,
result.nodes[current].maximum);
joined.linear = true;
joined.children = {top, current};
current = add_node(std::move(joined));
continue;
}
}
node_stack.push_back(current);
if (node_stack.size() == 1) {
break;
}
int left = result.nodes[node_stack.back()].left;
if (differences.prod(0, left) != 0) {
break;
}
int top = node_stack.back();
node_stack.pop_back();
common_interval_node prime = result.nodes[top];
prime.linear = false;
prime.children = {top};
current = add_node(std::move(prime));
do {
assert(!node_stack.empty());
top = node_stack.back();
node_stack.pop_back();
result.nodes[current].children.push_back(top);
result.nodes[current].left =
std::min(result.nodes[current].left, result.nodes[top].left);
result.nodes[current].right =
std::max(result.nodes[current].right, result.nodes[top].right);
result.nodes[current].minimum =
std::min(result.nodes[current].minimum, result.nodes[top].minimum);
result.nodes[current].maximum =
std::max(result.nodes[current].maximum, result.nodes[top].maximum);
} while (result.nodes[current].right - result.nodes[current].left !=
result.nodes[current].maximum - result.nodes[current].minimum);
std::reverse(result.nodes[current].children.begin(),
result.nodes[current].children.end());
}
differences.set(index, 0);
}
assert(node_stack.size() == 1);
result.root = node_stack.back();
return result;
}
} // namespace noya