This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub hitonanode/cplib-cpp
#include "other_algorithms/permutation_tree.hpp"
与えられた $[0, \dots, N - 1]$ の置換 $\mathbf{A} = [A_0, \dots, A_{N - 1}]$ について,この連続部分列であってその長さがそれに含まれる要素の最大値と最小値の差に $1$ を加えた値と等しくなるようなものを全て列挙するのに役立つデータ構造.
Permutation tree は区間のマージ過程を表す木として表現される.$N$ 個の葉は長さ $1$ の区間(単一の要素)に対応し,根は $\mathbf{A}$ 全体に対応する.
葉以外の全ての頂点は Join と Cut いずれかの属性を持つ.Join 属性を持つ頂点は,その子を $c_1, \dots, c_k$ とおくと,任意の $1 \le i \le j \le k$ について頂点 $(c_i, \dots, c_j)$ が表す区間の和集合は上記の条件を満たす.また,全ての頂点について,その頂点が表す区間全体は上記の条件を満たす.そして,上記の条件を満たす区間はこれらに限られるというのが最も重要な性質である.
Join
Cut
木の各頂点の情報はメンバ変数 std::vector<node> nodes に格納されている.特に根が格納されている位置を示す変数が tree.root.
std::vector<node> nodes
tree.root
enum NodeType { JoinAsc, // Join,特に A[i] の値が増加していく JoinDesc, // Join,特に A[i] の値が減少していく Cut, // Cut Leaf, // 葉である None, }; struct node { NodeType tp; int L, R; // [L, R) : 頂点が表す区間 int mini, maxi; // 区間に含まれる A[i] (L <= i < R) の最小・最大値 std::vector<int> child; // 子の頂点番号(昇順) };
また.to_DOT(std::string filename) によって DOT 言語でのグラフ出力が可能.
to_DOT(std::string filename)
上記の条件を満たす区間の個数だけを求めればよい問題.
permutation_tree tree(A); auto rec = [&](auto &&self, int now) -> long long { long long ret = 1; const auto &v = tree.nodes[now]; if (v.tp == permutation_tree::JoinAsc or v.tp == permutation_tree::JoinDesc) { ret = (long long)v.child.size() * (v.child.size() - 1) / 2; } for (auto c : v.child) ret += self(self, c); return ret; }; cout << rec(rec, tree.root) << '\n';
木上を DFS しながら DP の遷移をさせていけばよく,これは以下のように再帰的に書ける.
permutation_tree tree(P); vector dp(K + 1, vector<mint>(N + 1)); dp[0][0] = 1; auto rec = [&](auto &&self, int now) -> void { auto &v = tree.nodes[now]; if (v.tp == permutation_tree::Cut or v.tp == permutation_tree::Leaf) { for (int k = 0; k < K; ++k) dp[k + 1][v.R] += dp[k][v.L]; } vector<mint> sum(K); for (auto ch : v.child) { self(self, ch); if (v.tp == permutation_tree::JoinAsc or v.tp == permutation_tree::JoinDesc) { for (int k = 0; k < K; ++k) { dp[k + 1][tree.nodes[ch].R] += sum[k]; sum[k] += dp[k][tree.nodes[ch].L]; } } } }; rec(rec, tree.root); for (int i = 1; i <= K; i++) cout << dp[i][N].val() << '\n';
#pragma once #include "../segmenttree/range-add-range-min.hpp" #include <algorithm> #include <cassert> #include <fstream> #include <string> #include <vector> // Permutation tree // Complexity: O(N log N) // https://codeforces.com/blog/entry/78898 https://yukicoder.me/problems/no/1720 struct permutation_tree { enum NodeType { JoinAsc, JoinDesc, Cut, Leaf, None, }; struct node { NodeType tp; int L, R; // i in [L, R) int mini, maxi; // A[i] in [mini, maxi] std::vector<int> child; int sz() const { return R - L; } template <class OStream> friend OStream &operator<<(OStream &os, const node &n) { os << "[[" << n.L << ',' << n.R << ")(ch:"; for (auto i : n.child) os << i << ','; return os << ")(tp=" << n.tp << ")]"; } }; int root; std::vector<int> A; std::vector<node> nodes; void _add_child(int parid, int chid) { nodes[parid].child.push_back(chid); nodes[parid].L = std::min(nodes[parid].L, nodes[chid].L); nodes[parid].R = std::max(nodes[parid].R, nodes[chid].R); nodes[parid].mini = std::min(nodes[parid].mini, nodes[chid].mini); nodes[parid].maxi = std::max(nodes[parid].maxi, nodes[chid].maxi); } permutation_tree() : root(-1) {} permutation_tree(const std::vector<int> &A_) : root(-1), A(A_) { // A: nonempty perm., 0-origin assert(!A.empty()); RangeAddRangeMin<int> seg((std::vector<int>(A.size()))); std::vector<int> hi{-1}, lo{-1}; std::vector<int> st; for (int i = 0; i < int(A.size()); ++i) { while (hi.back() >= 0 and A[i] > A[hi.back()]) { seg.add(hi[hi.size() - 2] + 1, hi.back() + 1, A[i] - A[hi.back()]); hi.pop_back(); } hi.push_back(i); while (lo.back() >= 0 and A[i] < A[lo.back()]) { seg.add(lo[lo.size() - 2] + 1, lo.back() + 1, A[lo.back()] - A[i]); lo.pop_back(); } lo.push_back(i); int h = nodes.size(); nodes.push_back({NodeType::Leaf, i, i + 1, A[i], A[i], std::vector<int>{}}); while (true) { NodeType join_tp = NodeType::None; if (!st.empty() and nodes[st.back()].maxi + 1 == nodes[h].mini) join_tp = JoinAsc; if (!st.empty() and nodes[h].maxi + 1 == nodes[st.back()].mini) join_tp = JoinDesc; if (!st.empty() and join_tp != NodeType::None) { const node &vtp = nodes[st.back()]; // Insert v as the child of the top node in the stack if (join_tp == vtp.tp) { // Append child to existing Join node _add_child(st.back(), h); h = st.back(); st.pop_back(); } else { // Make new join node (with exactly two children) int j = st.back(); nodes.push_back( {join_tp, nodes[j].L, nodes[j].R, nodes[j].mini, nodes[j].maxi, {j}}); st.pop_back(); _add_child(nodes.size() - 1, h); h = nodes.size() - 1; } } else if (seg.prod(0, i + 1 - nodes[h].sz()) == 0) { // Make Cut node int L = nodes[h].L, R = nodes[h].R, maxi = nodes[h].maxi, mini = nodes[h].mini; nodes.push_back({NodeType::Cut, L, R, mini, maxi, {h}}); h = nodes.size() - 1; do { _add_child(h, st.back()); st.pop_back(); } while (nodes[h].maxi - nodes[h].mini + 1 != nodes[h].sz()); std::reverse(nodes[h].child.begin(), nodes[h].child.end()); } else { break; } } st.push_back(h); seg.add(0, i + 1, -1); } assert(st.size() == 1); root = st[0]; } void to_DOT(std::string filename = "") const { if (filename.empty()) filename = "permutation_tree_v=" + std::to_string(A.size()) + ".DOT"; std::ofstream ss(filename); ss << "digraph{\n"; int nleaf = 0; for (int i = 0; i < int(nodes.size()); i++) { ss << i << "[\n"; std::string lbl; if (nodes[i].tp == NodeType::Leaf) { lbl = "A[" + std::to_string(nleaf) + "] = " + std::to_string(A[nleaf]), nleaf++; } else { lbl += std::string(nodes[i].tp == NodeType::Cut ? "Cut" : "Join") + "\\n"; lbl += "[" + std::to_string(nodes[i].L) + ", " + std::to_string(nodes[i].R) + ")"; } ss << "label = \"" << lbl << "\",\n"; ss << "]\n"; for (const auto &ch : nodes[i].child) ss << i << " -> " << ch << ";\n"; } ss << "{rank = same;"; for (int i = 0; i < int(nodes.size()); i++) { if (nodes[i].tp == NodeType::Leaf) ss << ' ' << i << ';'; } ss << "}\n"; ss << "}\n"; ss.close(); } };
#line 2 "segmenttree/range-add-range-min.hpp" #include <algorithm> #include <limits> #include <vector> // CUT begin // StarrySkyTree: segment tree for Range Minimum Query & Range Add Query // Complexity: $O(N)$ (construction), $O(\log N)$ (add / get / prod) // - RangeAddRangeMin(std::vector<Tp> data_init) : Initialize array x by data_init. // - add(int begin, int end, Tp vadd) : Update x[i] <- x[i] + vadd for all begin <= i < end. // - get(int pos) : Get x[pos]. // - prod(int begin, int end) : Get min(x[begin], ..., x[end - 1]). template <typename Tp, Tp defaultT = std::numeric_limits<Tp>::max() / 2> struct RangeAddRangeMin { int N, head; std::vector<Tp> range_min, range_add; static inline Tp f(Tp x, Tp y) noexcept { return std::min(x, y); } inline void _merge(int pos) { range_min[pos] = f(range_min[pos * 2] + range_add[pos * 2], range_min[pos * 2 + 1] + range_add[pos * 2 + 1]); } void initialize(const std::vector<Tp> &data_init) { N = data_init.size(), head = 1; while (head < N) head <<= 1; range_min.assign(head * 2, defaultT); range_add.assign(head * 2, 0); std::copy(data_init.begin(), data_init.end(), range_min.begin() + head); for (int pos = head; --pos;) _merge(pos); } RangeAddRangeMin() = default; RangeAddRangeMin(const std::vector<Tp> &data_init) { initialize(data_init); } void _add(int begin, int end, int pos, int l, int r, Tp vadd) noexcept { if (r <= begin or end <= l) return; if (begin <= l and r <= end) { range_add[pos] += vadd; return; } _add(begin, end, pos * 2, l, (l + r) / 2, vadd); _add(begin, end, pos * 2 + 1, (l + r) / 2, r, vadd); _merge(pos); } // Add `vadd` to (x_begin, ..., x_{end - 1}) void add(int begin, int end, Tp vadd) noexcept { return _add(begin, end, 1, 0, head, vadd); } Tp _get(int begin, int end, int pos, int l, int r) const noexcept { if (r <= begin or end <= l) return defaultT; if (begin <= l and r <= end) return range_min[pos] + range_add[pos]; return f(_get(begin, end, pos * 2, l, (l + r) / 2), _get(begin, end, pos * 2 + 1, (l + r) / 2, r)) + range_add[pos]; } // Return f(x_begin, ..., x_{end - 1}) Tp get(int pos) const noexcept { return prod(pos, pos + 1); } Tp prod(int begin, int end) const noexcept { return _get(begin, end, 1, 0, head); } }; #line 4 "other_algorithms/permutation_tree.hpp" #include <cassert> #include <fstream> #include <string> #line 8 "other_algorithms/permutation_tree.hpp" // Permutation tree // Complexity: O(N log N) // https://codeforces.com/blog/entry/78898 https://yukicoder.me/problems/no/1720 struct permutation_tree { enum NodeType { JoinAsc, JoinDesc, Cut, Leaf, None, }; struct node { NodeType tp; int L, R; // i in [L, R) int mini, maxi; // A[i] in [mini, maxi] std::vector<int> child; int sz() const { return R - L; } template <class OStream> friend OStream &operator<<(OStream &os, const node &n) { os << "[[" << n.L << ',' << n.R << ")(ch:"; for (auto i : n.child) os << i << ','; return os << ")(tp=" << n.tp << ")]"; } }; int root; std::vector<int> A; std::vector<node> nodes; void _add_child(int parid, int chid) { nodes[parid].child.push_back(chid); nodes[parid].L = std::min(nodes[parid].L, nodes[chid].L); nodes[parid].R = std::max(nodes[parid].R, nodes[chid].R); nodes[parid].mini = std::min(nodes[parid].mini, nodes[chid].mini); nodes[parid].maxi = std::max(nodes[parid].maxi, nodes[chid].maxi); } permutation_tree() : root(-1) {} permutation_tree(const std::vector<int> &A_) : root(-1), A(A_) { // A: nonempty perm., 0-origin assert(!A.empty()); RangeAddRangeMin<int> seg((std::vector<int>(A.size()))); std::vector<int> hi{-1}, lo{-1}; std::vector<int> st; for (int i = 0; i < int(A.size()); ++i) { while (hi.back() >= 0 and A[i] > A[hi.back()]) { seg.add(hi[hi.size() - 2] + 1, hi.back() + 1, A[i] - A[hi.back()]); hi.pop_back(); } hi.push_back(i); while (lo.back() >= 0 and A[i] < A[lo.back()]) { seg.add(lo[lo.size() - 2] + 1, lo.back() + 1, A[lo.back()] - A[i]); lo.pop_back(); } lo.push_back(i); int h = nodes.size(); nodes.push_back({NodeType::Leaf, i, i + 1, A[i], A[i], std::vector<int>{}}); while (true) { NodeType join_tp = NodeType::None; if (!st.empty() and nodes[st.back()].maxi + 1 == nodes[h].mini) join_tp = JoinAsc; if (!st.empty() and nodes[h].maxi + 1 == nodes[st.back()].mini) join_tp = JoinDesc; if (!st.empty() and join_tp != NodeType::None) { const node &vtp = nodes[st.back()]; // Insert v as the child of the top node in the stack if (join_tp == vtp.tp) { // Append child to existing Join node _add_child(st.back(), h); h = st.back(); st.pop_back(); } else { // Make new join node (with exactly two children) int j = st.back(); nodes.push_back( {join_tp, nodes[j].L, nodes[j].R, nodes[j].mini, nodes[j].maxi, {j}}); st.pop_back(); _add_child(nodes.size() - 1, h); h = nodes.size() - 1; } } else if (seg.prod(0, i + 1 - nodes[h].sz()) == 0) { // Make Cut node int L = nodes[h].L, R = nodes[h].R, maxi = nodes[h].maxi, mini = nodes[h].mini; nodes.push_back({NodeType::Cut, L, R, mini, maxi, {h}}); h = nodes.size() - 1; do { _add_child(h, st.back()); st.pop_back(); } while (nodes[h].maxi - nodes[h].mini + 1 != nodes[h].sz()); std::reverse(nodes[h].child.begin(), nodes[h].child.end()); } else { break; } } st.push_back(h); seg.add(0, i + 1, -1); } assert(st.size() == 1); root = st[0]; } void to_DOT(std::string filename = "") const { if (filename.empty()) filename = "permutation_tree_v=" + std::to_string(A.size()) + ".DOT"; std::ofstream ss(filename); ss << "digraph{\n"; int nleaf = 0; for (int i = 0; i < int(nodes.size()); i++) { ss << i << "[\n"; std::string lbl; if (nodes[i].tp == NodeType::Leaf) { lbl = "A[" + std::to_string(nleaf) + "] = " + std::to_string(A[nleaf]), nleaf++; } else { lbl += std::string(nodes[i].tp == NodeType::Cut ? "Cut" : "Join") + "\\n"; lbl += "[" + std::to_string(nodes[i].L) + ", " + std::to_string(nodes[i].R) + ")"; } ss << "label = \"" << lbl << "\",\n"; ss << "]\n"; for (const auto &ch : nodes[i].child) ss << i << " -> " << ch << ";\n"; } ss << "{rank = same;"; for (int i = 0; i < int(nodes.size()); i++) { if (nodes[i].tp == NodeType::Leaf) ss << ' ' << i << ';'; } ss << "}\n"; ss << "}\n"; ss.close(); } };