common_interval_decomposition_tree.hpp¶
对两个排列构造公共区间树：若一组元素在两排列中分别对应连续下标段则称其为公共区间，树按该 laminar 家族分治分解并给出所有极大公共区间。
Complexity: Time: O(n log n). Space: O(n).
AC 记录：common_interval_decomposition_tree。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @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 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;
};
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 a, value_type b) { return std::max(a, b); }
};
struct addition_action {
using value_type = int;
static value_type unit() { return 0; }
static value_type composition(value_type nw, value_type old) {
return nw + old;
}
static int apply(value_type add, int val) { return val + add; }
};
} // 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> &p) {
int sz = int(p.size());
assert(sz > 0);
std::vector<bool> vis(sz);
for (int val : p) {
assert(0 <= val && val < sz);
assert(!vis[val]);
vis[val] = true;
}
using segment_tree = lazy_segtree<common_interval_internal::maximum_monoid,
common_interval_internal::addition_action>;
segment_tree seg(sz);
std::vector<int> smi;
std::vector<int> smx;
std::vector<int> st;
common_interval_tree res;
res.tr.reserve(sz * 2 - 1);
auto ins = [&](common_interval_node u) {
res.tr.push_back(std::move(u));
return int(res.tr.size()) - 1;
};
auto adj = [&](int a, int b) {
return res.tr[a].mn == res.tr[b].mx || res.tr[a].mx == res.tr[b].mn;
};
for (int idx = 0; idx < sz; idx++) {
int r = idx;
while (!smi.empty() && p[smi.back()] > p[idx]) {
smi.pop_back();
int l = smi.empty() ? 0 : smi.back() + 1;
seg.apply(l, r, p[idx] - p[r - 1]);
r = l;
}
smi.push_back(idx);
r = idx;
while (!smx.empty() && p[smx.back()] < p[idx]) {
smx.pop_back();
int l = smx.empty() ? 0 : smx.back() + 1;
seg.apply(l, r, -p[idx] + p[r - 1]);
r = l;
}
smx.push_back(idx);
seg.apply(0, idx, 1);
int cur =
ins(common_interval_node{idx, idx + 1, p[idx], p[idx] + 1, true, {}});
while (true) {
if (!st.empty()) {
int top = st.back();
if (res.tr[top].lin && !res.tr[top].ch.empty() &&
adj(cur, res.tr[top].ch.back())) {
st.pop_back();
res.tr[top].ch.push_back(cur);
res.tr[top].l = std::min(res.tr[top].l, res.tr[cur].l);
res.tr[top].r = std::max(res.tr[top].r, res.tr[cur].r);
res.tr[top].mn = std::min(res.tr[top].mn, res.tr[cur].mn);
res.tr[top].mx = std::max(res.tr[top].mx, res.tr[cur].mx);
cur = top;
continue;
}
if (adj(top, cur)) {
st.pop_back();
common_interval_node tmp;
tmp.l = res.tr[top].l;
tmp.r = res.tr[cur].r;
tmp.mn = std::min(res.tr[top].mn, res.tr[cur].mn);
tmp.mx = std::max(res.tr[top].mx, res.tr[cur].mx);
tmp.lin = true;
tmp.ch = {top, cur};
cur = ins(std::move(tmp));
continue;
}
}
st.push_back(cur);
if (st.size() == 1) {
break;
}
int l = res.tr[st.back()].l;
if (seg.prod(0, l) != 0) {
break;
}
int top = st.back();
st.pop_back();
common_interval_node tm = res.tr[top];
tm.lin = false;
tm.ch = {top};
cur = ins(std::move(tm));
do {
assert(!st.empty());
top = st.back();
st.pop_back();
res.tr[cur].ch.push_back(top);
res.tr[cur].l = std::min(res.tr[cur].l, res.tr[top].l);
res.tr[cur].r = std::max(res.tr[cur].r, res.tr[top].r);
res.tr[cur].mn = std::min(res.tr[cur].mn, res.tr[top].mn);
res.tr[cur].mx = std::max(res.tr[cur].mx, res.tr[top].mx);
} while (res.tr[cur].r - res.tr[cur].l !=
res.tr[cur].mx - res.tr[cur].mn);
std::reverse(res.tr[cur].ch.begin(), res.tr[cur].ch.end());
}
seg.set(idx, 0);
}
assert(st.size() == 1);
res.rt = st.back();
return res;
}
} // namespace noya
#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 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;
};
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 a, value_type b) { return std::max(a, b); }
};
struct addition_action {
using value_type = int;
static value_type unit() { return 0; }
static value_type composition(value_type nw, value_type old) {
return nw + old;
}
static int apply(value_type add, int val) { return val + add; }
};
} // 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> &p) {
int sz = int(p.size());
assert(sz > 0);
std::vector<bool> vis(sz);
for (int val : p) {
assert(0 <= val && val < sz);
assert(!vis[val]);
vis[val] = true;
}
using segment_tree = lazy_segtree<common_interval_internal::maximum_monoid,
common_interval_internal::addition_action>;
segment_tree seg(sz);
std::vector<int> smi;
std::vector<int> smx;
std::vector<int> st;
common_interval_tree res;
res.tr.reserve(sz * 2 - 1);
auto ins = [&](common_interval_node u) {
res.tr.push_back(std::move(u));
return int(res.tr.size()) - 1;
};
auto adj = [&](int a, int b) {
return res.tr[a].mn == res.tr[b].mx || res.tr[a].mx == res.tr[b].mn;
};
for (int idx = 0; idx < sz; idx++) {
int r = idx;
while (!smi.empty() && p[smi.back()] > p[idx]) {
smi.pop_back();
int l = smi.empty() ? 0 : smi.back() + 1;
seg.apply(l, r, p[idx] - p[r - 1]);
r = l;
}
smi.push_back(idx);
r = idx;
while (!smx.empty() && p[smx.back()] < p[idx]) {
smx.pop_back();
int l = smx.empty() ? 0 : smx.back() + 1;
seg.apply(l, r, -p[idx] + p[r - 1]);
r = l;
}
smx.push_back(idx);
seg.apply(0, idx, 1);
int cur =
ins(common_interval_node{idx, idx + 1, p[idx], p[idx] + 1, true, {}});
while (true) {
if (!st.empty()) {
int top = st.back();
if (res.tr[top].lin && !res.tr[top].ch.empty() &&
adj(cur, res.tr[top].ch.back())) {
st.pop_back();
res.tr[top].ch.push_back(cur);
res.tr[top].l = std::min(res.tr[top].l, res.tr[cur].l);
res.tr[top].r = std::max(res.tr[top].r, res.tr[cur].r);
res.tr[top].mn = std::min(res.tr[top].mn, res.tr[cur].mn);
res.tr[top].mx = std::max(res.tr[top].mx, res.tr[cur].mx);
cur = top;
continue;
}
if (adj(top, cur)) {
st.pop_back();
common_interval_node tmp;
tmp.l = res.tr[top].l;
tmp.r = res.tr[cur].r;
tmp.mn = std::min(res.tr[top].mn, res.tr[cur].mn);
tmp.mx = std::max(res.tr[top].mx, res.tr[cur].mx);
tmp.lin = true;
tmp.ch = {top, cur};
cur = ins(std::move(tmp));
continue;
}
}
st.push_back(cur);
if (st.size() == 1) {
break;
}
int l = res.tr[st.back()].l;
if (seg.prod(0, l) != 0) {
break;
}
int top = st.back();
st.pop_back();
common_interval_node tm = res.tr[top];
tm.lin = false;
tm.ch = {top};
cur = ins(std::move(tm));
do {
assert(!st.empty());
top = st.back();
st.pop_back();
res.tr[cur].ch.push_back(top);
res.tr[cur].l = std::min(res.tr[cur].l, res.tr[top].l);
res.tr[cur].r = std::max(res.tr[cur].r, res.tr[top].r);
res.tr[cur].mn = std::min(res.tr[cur].mn, res.tr[top].mn);
res.tr[cur].mx = std::max(res.tr[cur].mx, res.tr[top].mx);
} while (res.tr[cur].r - res.tr[cur].l !=
res.tr[cur].mx - res.tr[cur].mn);
std::reverse(res.tr[cur].ch.begin(), res.tr[cur].ch.end());
}
seg.set(idx, 0);
}
assert(st.size() == 1);
res.rt = st.back();
return res;
}
} // 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(l, r)`.
/// Action provides `value_type`, `unit()`, `composition(newer, older)`, and
/// `apply(tag, 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 sz = 1;
int log = 0;
std::vector<S> dat;
std::vector<F> lz;
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n_) { build(n_); }
explicit lazy_segtree(const std::vector<S> &a) { build(a); }
void build(int n_) { build(std::vector<S>(n_, Monoid::unit())); }
void build(const std::vector<S> &a) {
n = int(a.size());
sz = 1;
log = 0;
while (sz < n) {
sz <<= 1;
log++;
}
dat.assign(sz << 1, Monoid::unit());
lz.assign(sz, Action::unit());
for (int i = 0; i < n; i++) {
dat[sz + i] = a[i];
}
for (int u = sz - 1; u >= 1; u--) {
pull(u);
}
}
void set(int pos, const S &val) {
assert(0 <= pos && pos < n);
pos += sz;
for (int h = log; h >= 1; h--) {
push(pos >> h);
}
dat[pos] = val;
for (int h = 1; h <= log; h++) {
pull(pos >> h);
}
}
S get(int pos) {
assert(0 <= pos && pos < n);
pos += sz;
for (int h = log; h >= 1; h--) {
push(pos >> h);
}
return dat[pos];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return Monoid::unit();
}
l += sz;
r += sz;
for (int h = log; h >= 1; h--) {
if (((l >> h) << h) != l) {
push(l >> h);
}
if (((r >> h) << h) != r) {
push((r - 1) >> h);
}
}
S arr = Monoid::unit();
S b = Monoid::unit();
while (l < r) {
if (l & 1) {
arr = Monoid::op(arr, dat[l++]);
}
if (r & 1) {
b = Monoid::op(dat[--r], b);
}
l >>= 1;
r >>= 1;
}
return Monoid::op(arr, b);
}
S all_prod() const { return dat[1]; }
/// @brief Apply an action to every element in [l, r).
void apply(int l, int r, const F &tag) {
assert(0 <= l && l <= r && r <= n);
if (l == r) {
return;
}
l += sz;
r += sz;
for (int h = log; h >= 1; h--) {
if (((l >> h) << h) != l) {
push(l >> h);
}
if (((r >> h) << h) != r) {
push((r - 1) >> h);
}
}
int l0 = l;
int r0 = r;
while (l < r) {
if (l & 1) {
all_apply(l++, tag);
}
if (r & 1) {
all_apply(--r, tag);
}
l >>= 1;
r >>= 1;
}
l = l0;
r = r0;
for (int h = 1; h <= log; h++) {
if (((l >> h) << h) != l) {
pull(l >> h);
}
if (((r >> h) << h) != r) {
pull((r - 1) >> h);
}
}
}
private:
void pull(int u) {
dat[u] = Monoid::op(dat[u << 1], dat[u << 1 | 1]);
}
void all_apply(int u, const F &tag) {
dat[u] = Action::apply(tag, dat[u]);
if (u < sz) {
lz[u] = Action::composition(tag, lz[u]);
}
}
void push(int u) {
all_apply(u << 1, lz[u]);
all_apply(u << 1 | 1, lz[u]);
lz[u] = Action::unit();
}
};
} // namespace noya
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;
};
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 a, value_type b) { return std::max(a, b); }
};
struct addition_action {
using value_type = int;
static value_type unit() { return 0; }
static value_type composition(value_type nw, value_type old) {
return nw + old;
}
static int apply(value_type add, int val) { return val + add; }
};
} // 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> &p) {
int sz = int(p.size());
assert(sz > 0);
std::vector<bool> vis(sz);
for (int val : p) {
assert(0 <= val && val < sz);
assert(!vis[val]);
vis[val] = true;
}
using segment_tree = lazy_segtree<common_interval_internal::maximum_monoid,
common_interval_internal::addition_action>;
segment_tree seg(sz);
std::vector<int> smi;
std::vector<int> smx;
std::vector<int> st;
common_interval_tree res;
res.tr.reserve(sz * 2 - 1);
auto ins = [&](common_interval_node u) {
res.tr.push_back(std::move(u));
return int(res.tr.size()) - 1;
};
auto adj = [&](int a, int b) {
return res.tr[a].mn == res.tr[b].mx || res.tr[a].mx == res.tr[b].mn;
};
for (int idx = 0; idx < sz; idx++) {
int r = idx;
while (!smi.empty() && p[smi.back()] > p[idx]) {
smi.pop_back();
int l = smi.empty() ? 0 : smi.back() + 1;
seg.apply(l, r, p[idx] - p[r - 1]);
r = l;
}
smi.push_back(idx);
r = idx;
while (!smx.empty() && p[smx.back()] < p[idx]) {
smx.pop_back();
int l = smx.empty() ? 0 : smx.back() + 1;
seg.apply(l, r, -p[idx] + p[r - 1]);
r = l;
}
smx.push_back(idx);
seg.apply(0, idx, 1);
int cur =
ins(common_interval_node{idx, idx + 1, p[idx], p[idx] + 1, true, {}});
while (true) {
if (!st.empty()) {
int top = st.back();
if (res.tr[top].lin && !res.tr[top].ch.empty() &&
adj(cur, res.tr[top].ch.back())) {
st.pop_back();
res.tr[top].ch.push_back(cur);
res.tr[top].l = std::min(res.tr[top].l, res.tr[cur].l);
res.tr[top].r = std::max(res.tr[top].r, res.tr[cur].r);
res.tr[top].mn = std::min(res.tr[top].mn, res.tr[cur].mn);
res.tr[top].mx = std::max(res.tr[top].mx, res.tr[cur].mx);
cur = top;
continue;
}
if (adj(top, cur)) {
st.pop_back();
common_interval_node tmp;
tmp.l = res.tr[top].l;
tmp.r = res.tr[cur].r;
tmp.mn = std::min(res.tr[top].mn, res.tr[cur].mn);
tmp.mx = std::max(res.tr[top].mx, res.tr[cur].mx);
tmp.lin = true;
tmp.ch = {top, cur};
cur = ins(std::move(tmp));
continue;
}
}
st.push_back(cur);
if (st.size() == 1) {
break;
}
int l = res.tr[st.back()].l;
if (seg.prod(0, l) != 0) {
break;
}
int top = st.back();
st.pop_back();
common_interval_node tm = res.tr[top];
tm.lin = false;
tm.ch = {top};
cur = ins(std::move(tm));
do {
assert(!st.empty());
top = st.back();
st.pop_back();
res.tr[cur].ch.push_back(top);
res.tr[cur].l = std::min(res.tr[cur].l, res.tr[top].l);
res.tr[cur].r = std::max(res.tr[cur].r, res.tr[top].r);
res.tr[cur].mn = std::min(res.tr[cur].mn, res.tr[top].mn);
res.tr[cur].mx = std::max(res.tr[cur].mx, res.tr[top].mx);
} while (res.tr[cur].r - res.tr[cur].l !=
res.tr[cur].mx - res.tr[cur].mn);
std::reverse(res.tr[cur].ch.begin(), res.tr[cur].ch.end());
}
seg.set(idx, 0);
}
assert(st.size() == 1);
res.rt = st.back();
return res;
}
} // namespace noya