rooted_tree_minimum_inversion_order.hpp¶
为有根树安排满足祖先约束的线性序，使给定权值产生的逆序对最少。
Complexity: Time: O(n log n). Space: O(n).
AC 记录：rooted_tree_topological_order_with_minimum_inversions。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log n). Space: O(n).
#include <algorithm>
#include <cassert>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct rooted_tree_minimum_inversion_order_result {
Weight cst{};
std::vector<int> ord;
};
namespace internal {
class labeled_dsu {
std::vector<int> fa_;
std::vector<int> id_;
int leader(int u) {
int rt = u;
while (fa_[rt] >= 0) {
rt = fa_[rt];
}
while (u != rt) {
int nxt = fa_[u];
fa_[u] = rt;
u = nxt;
}
return rt;
}
public:
explicit labeled_dsu(int siz) : fa_(siz, -1), id_(siz) {
std::iota(id_.begin(), id_.end(), 0);
}
int label(int u) { return id_[leader(u)]; }
void merge(int a, int b, int nl) {
a = leader(a);
b = leader(b);
assert(a != b);
if (fa_[a] > fa_[b]) {
std::swap(a, b);
}
fa_[a] += fa_[b];
fa_[b] = a;
id_[a] = nl;
}
};
} // namespace internal
/// @brief Find a parent-before-child order minimizing the weighted inversion
/// cost. For two independent blocks A and B, placing A first contributes
/// d(A)c(B), while placing B first contributes d(B)c(A); hence the better
/// block order is decreasing c/d. Sidney's decomposition for an out-tree is
/// obtained by repeatedly contracting the maximum-ratio non-root block into
/// its parent block. A labeled DSU finds that current parent block, while a
/// cyclic linked list records the corresponding concatenations. The returned
/// cost is sum over i < j of d[ord[i]] * c[ord[j]]. All weights must be
/// nonnegative, and Weight must hold aggregate sums and their products.
template <class Weight>
rooted_tree_minimum_inversion_order_result<Weight>
rooted_tree_minimum_inversion_order(const std::vector<int> &fa,
const std::vector<Weight> &c,
const std::vector<Weight> &d) {
int siz = int(fa.size());
assert(siz > 0);
assert(int(c.size()) == siz && int(d.size()) == siz);
int rt = -1;
for (int u = 0; u < siz; u++) {
assert(c[u] >= Weight{} && d[u] >= Weight{});
if (fa[u] == -1) {
assert(rt == -1);
rt = u;
} else {
assert(0 <= fa[u] && fa[u] < siz);
assert(fa[u] != u);
}
}
assert(rt != -1);
struct block {
Weight d;
Weight c;
int rt;
int ver;
};
struct lower_priority {
static bool ratio_less(const block &l, const block &r) {
bool lz = l.c == Weight{} && l.d == Weight{};
bool rz = r.c == Weight{} && r.d == Weight{};
if (lz != rz) {
return lz;
}
if (lz) {
return false;
}
return l.c * r.d < l.d * r.c;
}
bool operator()(const block &l, const block &r) const {
if (ratio_less(l, r)) {
return true;
}
if (ratio_less(r, l)) {
return false;
}
return std::tie(l.rt, l.ver) < std::tie(r.rt, r.ver);
}
};
std::vector<Weight> bc = c;
std::vector<Weight> bd = d;
std::vector<int> ver(siz);
std::priority_queue<block, std::vector<block>, lower_priority> q;
for (int u = 0; u < siz; u++) {
if (u != rt) {
q.push({bd[u], bc[u], u, 0});
}
}
internal::labeled_dsu dsu(siz);
std::vector<int> nxt(siz);
std::iota(nxt.begin(), nxt.end(), 0);
while (!q.empty()) {
block cur = q.top();
q.pop();
int u = cur.rt;
if (cur.ver != ver[u]) {
continue;
}
int bp = dsu.label(fa[u]);
bc[bp] += bc[u];
bd[bp] += bd[u];
dsu.merge(u, bp, bp);
if (bp != rt) {
int ve1 = ++ver[bp];
q.push({bd[bp], bc[bp], bp, ve1});
}
std::swap(nxt[u], nxt[bp]);
}
rooted_tree_minimum_inversion_order_result<Weight> res;
res.ord.reserve(siz);
int u = rt;
for (int i = 0; i < siz; i++) {
u = nxt[u];
res.ord.push_back(u);
}
assert(u == rt);
std::reverse(res.ord.begin(), res.ord.end());
Weight pd{};
for (int cur : res.ord) {
res.cst += pd * c[cur];
pd += d[cur];
}
return res;
}
} // namespace noya
#ifndef NOYA_ROOTED_TREE_MINIMUM_INVERSION_ORDER_HPP
#define NOYA_ROOTED_TREE_MINIMUM_INVERSION_ORDER_HPP 1
/// @complexity Time: O(n log n). Space: O(n).
#include <algorithm>
#include <cassert>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
namespace noya {
template <class Weight> struct rooted_tree_minimum_inversion_order_result {
Weight cst{};
std::vector<int> ord;
};
namespace internal {
class labeled_dsu {
std::vector<int> fa_;
std::vector<int> id_;
int leader(int u) {
int rt = u;
while (fa_[rt] >= 0) {
rt = fa_[rt];
}
while (u != rt) {
int nxt = fa_[u];
fa_[u] = rt;
u = nxt;
}
return rt;
}
public:
explicit labeled_dsu(int siz) : fa_(siz, -1), id_(siz) {
std::iota(id_.begin(), id_.end(), 0);
}
int label(int u) { return id_[leader(u)]; }
void merge(int a, int b, int nl) {
a = leader(a);
b = leader(b);
assert(a != b);
if (fa_[a] > fa_[b]) {
std::swap(a, b);
}
fa_[a] += fa_[b];
fa_[b] = a;
id_[a] = nl;
}
};
} // namespace internal
/// @brief Find a parent-before-child order minimizing the weighted inversion
/// cost. For two independent blocks A and B, placing A first contributes
/// d(A)c(B), while placing B first contributes d(B)c(A); hence the better
/// block order is decreasing c/d. Sidney's decomposition for an out-tree is
/// obtained by repeatedly contracting the maximum-ratio non-root block into
/// its parent block. A labeled DSU finds that current parent block, while a
/// cyclic linked list records the corresponding concatenations. The returned
/// cost is sum over i < j of d[ord[i]] * c[ord[j]]. All weights must be
/// nonnegative, and Weight must hold aggregate sums and their products.
template <class Weight>
rooted_tree_minimum_inversion_order_result<Weight>
rooted_tree_minimum_inversion_order(const std::vector<int> &fa,
const std::vector<Weight> &c,
const std::vector<Weight> &d) {
int siz = int(fa.size());
assert(siz > 0);
assert(int(c.size()) == siz && int(d.size()) == siz);
int rt = -1;
for (int u = 0; u < siz; u++) {
assert(c[u] >= Weight{} && d[u] >= Weight{});
if (fa[u] == -1) {
assert(rt == -1);
rt = u;
} else {
assert(0 <= fa[u] && fa[u] < siz);
assert(fa[u] != u);
}
}
assert(rt != -1);
struct block {
Weight d;
Weight c;
int rt;
int ver;
};
struct lower_priority {
static bool ratio_less(const block &l, const block &r) {
bool lz = l.c == Weight{} && l.d == Weight{};
bool rz = r.c == Weight{} && r.d == Weight{};
if (lz != rz) {
return lz;
}
if (lz) {
return false;
}
return l.c * r.d < l.d * r.c;
}
bool operator()(const block &l, const block &r) const {
if (ratio_less(l, r)) {
return true;
}
if (ratio_less(r, l)) {
return false;
}
return std::tie(l.rt, l.ver) < std::tie(r.rt, r.ver);
}
};
std::vector<Weight> bc = c;
std::vector<Weight> bd = d;
std::vector<int> ver(siz);
std::priority_queue<block, std::vector<block>, lower_priority> q;
for (int u = 0; u < siz; u++) {
if (u != rt) {
q.push({bd[u], bc[u], u, 0});
}
}
internal::labeled_dsu dsu(siz);
std::vector<int> nxt(siz);
std::iota(nxt.begin(), nxt.end(), 0);
while (!q.empty()) {
block cur = q.top();
q.pop();
int u = cur.rt;
if (cur.ver != ver[u]) {
continue;
}
int bp = dsu.label(fa[u]);
bc[bp] += bc[u];
bd[bp] += bd[u];
dsu.merge(u, bp, bp);
if (bp != rt) {
int ve1 = ++ver[bp];
q.push({bd[bp], bc[bp], bp, ve1});
}
std::swap(nxt[u], nxt[bp]);
}
rooted_tree_minimum_inversion_order_result<Weight> res;
res.ord.reserve(siz);
int u = rt;
for (int i = 0; i < siz; i++) {
u = nxt[u];
res.ord.push_back(u);
}
assert(u == rt);
std::reverse(res.ord.begin(), res.ord.end());
Weight pd{};
for (int cur : res.ord) {
res.cst += pd * c[cur];
pd += d[cur];
}
return res;
}
} // namespace noya
#endif // NOYA_ROOTED_TREE_MINIMUM_INVERSION_ORDER_HPP
#include <algorithm>
#include <cassert>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
/// @complexity Time: O(n log n). Space: O(n).
namespace noya {
template <class Weight> struct rooted_tree_minimum_inversion_order_result {
Weight cst{};
std::vector<int> ord;
};
namespace internal {
class labeled_dsu {
std::vector<int> fa_;
std::vector<int> id_;
int leader(int u) {
int rt = u;
while (fa_[rt] >= 0) {
rt = fa_[rt];
}
while (u != rt) {
int nxt = fa_[u];
fa_[u] = rt;
u = nxt;
}
return rt;
}
public:
explicit labeled_dsu(int siz) : fa_(siz, -1), id_(siz) {
std::iota(id_.begin(), id_.end(), 0);
}
int label(int u) { return id_[leader(u)]; }
void merge(int a, int b, int nl) {
a = leader(a);
b = leader(b);
assert(a != b);
if (fa_[a] > fa_[b]) {
std::swap(a, b);
}
fa_[a] += fa_[b];
fa_[b] = a;
id_[a] = nl;
}
};
} // namespace internal
/// @brief Find a parent-before-child order minimizing the weighted inversion
/// cost. For two independent blocks A and B, placing A first contributes
/// d(A)c(B), while placing B first contributes d(B)c(A); hence the better
/// block order is decreasing c/d. Sidney's decomposition for an out-tree is
/// obtained by repeatedly contracting the maximum-ratio non-root block into
/// its parent block. A labeled DSU finds that current parent block, while a
/// cyclic linked list records the corresponding concatenations. The returned
/// cost is sum over i < j of d[ord[i]] * c[ord[j]]. All weights must be
/// nonnegative, and Weight must hold aggregate sums and their products.
template <class Weight>
rooted_tree_minimum_inversion_order_result<Weight>
rooted_tree_minimum_inversion_order(const std::vector<int> &fa,
const std::vector<Weight> &c,
const std::vector<Weight> &d) {
int siz = int(fa.size());
assert(siz > 0);
assert(int(c.size()) == siz && int(d.size()) == siz);
int rt = -1;
for (int u = 0; u < siz; u++) {
assert(c[u] >= Weight{} && d[u] >= Weight{});
if (fa[u] == -1) {
assert(rt == -1);
rt = u;
} else {
assert(0 <= fa[u] && fa[u] < siz);
assert(fa[u] != u);
}
}
assert(rt != -1);
struct block {
Weight d;
Weight c;
int rt;
int ver;
};
struct lower_priority {
static bool ratio_less(const block &l, const block &r) {
bool lz = l.c == Weight{} && l.d == Weight{};
bool rz = r.c == Weight{} && r.d == Weight{};
if (lz != rz) {
return lz;
}
if (lz) {
return false;
}
return l.c * r.d < l.d * r.c;
}
bool operator()(const block &l, const block &r) const {
if (ratio_less(l, r)) {
return true;
}
if (ratio_less(r, l)) {
return false;
}
return std::tie(l.rt, l.ver) < std::tie(r.rt, r.ver);
}
};
std::vector<Weight> bc = c;
std::vector<Weight> bd = d;
std::vector<int> ver(siz);
std::priority_queue<block, std::vector<block>, lower_priority> q;
for (int u = 0; u < siz; u++) {
if (u != rt) {
q.push({bd[u], bc[u], u, 0});
}
}
internal::labeled_dsu dsu(siz);
std::vector<int> nxt(siz);
std::iota(nxt.begin(), nxt.end(), 0);
while (!q.empty()) {
block cur = q.top();
q.pop();
int u = cur.rt;
if (cur.ver != ver[u]) {
continue;
}
int bp = dsu.label(fa[u]);
bc[bp] += bc[u];
bd[bp] += bd[u];
dsu.merge(u, bp, bp);
if (bp != rt) {
int ve1 = ++ver[bp];
q.push({bd[bp], bc[bp], bp, ve1});
}
std::swap(nxt[u], nxt[bp]);
}
rooted_tree_minimum_inversion_order_result<Weight> res;
res.ord.reserve(siz);
int u = rt;
for (int i = 0; i < siz; i++) {
u = nxt[u];
res.ord.push_back(u);
}
assert(u == rt);
std::reverse(res.ord.begin(), res.ord.end());
Weight pd{};
for (int cur : res.ord) {
res.cst += pd * c[cur];
pd += d[cur];
}
return res;
}
} // namespace noya