sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "tree/permutation_tree.hpp"
Permutation tree は,順列の区間のマージ過程を表す木である.$\max_{l\leq i < r} p_i - \min_{l\leq i < r} p_i = r - l$ となるような区間の数え上げなどに使える.
PermutationTree(vector<int> p)
#pragma once #include <algorithm> #include <vector> #include "../data-structure/segtree/lazy_segment_tree.hpp" struct MinMonoid { using T = int; static T id() { return (1u << 31) - 1; } static T op(T a, T b) { return std::min(a, b); } }; struct AddMonoid { using T = int; static T id() { return 0; } static T op(T a, T b) { return a + b; } }; int act(int a, int b) { return a + b; } class PermutationTree { public: enum NodeType { JoinAsc, JoinDesc, Cut, Leaf, None }; struct Node { NodeType tp; int l, r; // i in [l, r) int lb, ub; // p[i] in [lb, ub) std::vector<int> ch; }; std::vector<Node> nodes; PermutationTree() = default; explicit PermutationTree(const std::vector<int>& p) { LazySegmentTree<MinMonoid, AddMonoid, act> seg( std::vector<int>(p.size())); // seg.fold(l, r) == // min_{l <= j < r} { max(p[j:i]) - min(p[j:i]) - (i - j) } std::vector<int> st_max = {-1}, st_min = {-1}, st; for (int i = 0; i < (int)p.size(); ++i) { while (st_max.back() >= 0 && p[st_max.back()] < p[i]) { seg.update(st_max[st_max.size() - 2] + 1, st_max.back() + 1, p[i] - p[st_max.back()]); st_max.pop_back(); } st_max.push_back(i); while (st_min.back() >= 0 && p[st_min.back()] > p[i]) { seg.update(st_min[st_min.size() - 2] + 1, st_min.back() + 1, -(p[i] - p[st_min.back()])); st_min.pop_back(); } st_min.push_back(i); nodes.push_back( {Leaf, i, i + 1, p[i], p[i] + 1, std::vector<int>{}}); int v = nodes.size() - 1; // index of the current node while (true) { NodeType join_tp = None; if (!st.empty() && nodes[st.back()].ub == nodes[v].lb) join_tp = JoinAsc; if (!st.empty() && nodes[st.back()].lb == nodes[v].ub) join_tp = JoinDesc; if (!st.empty() && join_tp != None) { // join if (join_tp == nodes[st.back()].tp) { // same type, append to the existing join node add_child(st.back(), v); v = st.back(); st.pop_back(); } else { // different type, create a new join node int u = st.back(); nodes.push_back({join_tp, nodes[u].l, nodes[u].r, nodes[u].lb, nodes[u].ub, {u}}); st.pop_back(); add_child(nodes.size() - 1, v); v = nodes.size() - 1; } } else if (seg.fold(0, i + 1 - (nodes[v].r - nodes[v].l)) == 0) { // cut int l = nodes[v].l, r = nodes[v].r, lb = nodes[v].lb, ub = nodes[v].ub; nodes.push_back({Cut, l, r, lb, ub, {v}}); v = nodes.size() - 1; do { add_child(v, st.back()); st.pop_back(); } while (nodes[v].ub - nodes[v].lb != nodes[v].r - nodes[v].l); std::ranges::reverse(nodes[v].ch); } else { break; } } st.push_back(v); seg.update(0, i + 1, -1); } } private: void add_child(int par, int ch) { nodes[par].ch.push_back(ch); nodes[par].l = std::min(nodes[par].l, nodes[ch].l); nodes[par].r = std::max(nodes[par].r, nodes[ch].r); nodes[par].lb = std::min(nodes[par].lb, nodes[ch].lb); nodes[par].ub = std::max(nodes[par].ub, nodes[ch].ub); } };
#line 2 "tree/permutation_tree.hpp" #include <algorithm> #include <vector> #line 3 "data-structure/segtree/lazy_segment_tree.hpp" #include <bit> #include <numeric> #line 6 "data-structure/segtree/lazy_segment_tree.hpp" template <typename M, typename O, typename M::T (*act)(typename M::T, typename O::T)> class LazySegmentTree { using T = M::T; using E = O::T; public: LazySegmentTree() = default; explicit LazySegmentTree(int n) : LazySegmentTree(std::vector<T>(n, M::id())) {} explicit LazySegmentTree(const std::vector<T>& v) : size(std::bit_ceil(v.size())), node(2 * size, M::id()), lazy(2 * size, O::id()) { std::ranges::copy(v, node.begin() + size); for (int i = size - 1; i > 0; --i) { node[i] = M::op(node[2 * i], node[2 * i + 1]); } } T operator[](int k) { return fold(k, k + 1); } void update(int l, int r, const E& x) { update(l, r, x, 1, 0, size); } T fold(int l, int r) { return fold(l, r, 1, 0, size); } T fold_all() { push(1); return node[1]; } template <typename F> int find_first(int l, F cond) { T v = M::id(); return find_first(l, size, 1, 0, size, v, cond); } template <typename F> int find_last(int r, F cond) { T v = M::id(); return find_last(0, r, 1, 0, size, v, cond); } private: int size; std::vector<T> node; std::vector<E> lazy; void push(int k) { if (lazy[k] == O::id()) return; if (k < size) { lazy[2 * k] = O::op(lazy[2 * k], lazy[k]); lazy[2 * k + 1] = O::op(lazy[2 * k + 1], lazy[k]); } node[k] = act(node[k], lazy[k]); lazy[k] = O::id(); } void update(int a, int b, const E& x, int k, int l, int r) { push(k); if (r <= a || b <= l) return; if (a <= l && r <= b) { lazy[k] = O::op(lazy[k], x); push(k); return; } int m = std::midpoint(l, r); update(a, b, x, 2 * k, l, m); update(a, b, x, 2 * k + 1, m, r); node[k] = M::op(node[2 * k], node[2 * k + 1]); } T fold(int a, int b, int k, int l, int r) { push(k); if (r <= a || b <= l) return M::id(); if (a <= l && r <= b) return node[k]; int m = std::midpoint(l, r); return M::op(fold(a, b, 2 * k, l, m), fold(a, b, 2 * k + 1, m, r)); } template <typename F> int find_first(int a, int b, int k, int l, int r, T& v, F cond) { push(k); if (r <= a) return -1; if (b <= l) return l; if (a <= l && r <= b && !cond(M::op(v, node[k]))) { v = M::op(v, node[k]); return -1; } if (r - l == 1) return r; int m = std::midpoint(l, r); int res = find_first(a, b, 2 * k, l, m, v, cond); if (res != -1) return res; return find_first(a, b, 2 * k + 1, m, r, v, cond); } template <typename F> int find_last(int a, int b, int k, int l, int r, T& v, F cond) { push(k); if (b <= l) return -1; if (r <= a) return r; if (a <= l && r <= b && !cond(M::op(node[k], v))) { v = M::op(node[k], v); return -1; } if (r - l == 1) return l; int m = std::midpoint(l, r); int res = find_last(a, b, 2 * k + 1, m, r, v, cond); if (res != -1) return res; return find_last(a, b, 2 * k, l, m, v, cond); } }; #line 6 "tree/permutation_tree.hpp" struct MinMonoid { using T = int; static T id() { return (1u << 31) - 1; } static T op(T a, T b) { return std::min(a, b); } }; struct AddMonoid { using T = int; static T id() { return 0; } static T op(T a, T b) { return a + b; } }; int act(int a, int b) { return a + b; } class PermutationTree { public: enum NodeType { JoinAsc, JoinDesc, Cut, Leaf, None }; struct Node { NodeType tp; int l, r; // i in [l, r) int lb, ub; // p[i] in [lb, ub) std::vector<int> ch; }; std::vector<Node> nodes; PermutationTree() = default; explicit PermutationTree(const std::vector<int>& p) { LazySegmentTree<MinMonoid, AddMonoid, act> seg( std::vector<int>(p.size())); // seg.fold(l, r) == // min_{l <= j < r} { max(p[j:i]) - min(p[j:i]) - (i - j) } std::vector<int> st_max = {-1}, st_min = {-1}, st; for (int i = 0; i < (int)p.size(); ++i) { while (st_max.back() >= 0 && p[st_max.back()] < p[i]) { seg.update(st_max[st_max.size() - 2] + 1, st_max.back() + 1, p[i] - p[st_max.back()]); st_max.pop_back(); } st_max.push_back(i); while (st_min.back() >= 0 && p[st_min.back()] > p[i]) { seg.update(st_min[st_min.size() - 2] + 1, st_min.back() + 1, -(p[i] - p[st_min.back()])); st_min.pop_back(); } st_min.push_back(i); nodes.push_back( {Leaf, i, i + 1, p[i], p[i] + 1, std::vector<int>{}}); int v = nodes.size() - 1; // index of the current node while (true) { NodeType join_tp = None; if (!st.empty() && nodes[st.back()].ub == nodes[v].lb) join_tp = JoinAsc; if (!st.empty() && nodes[st.back()].lb == nodes[v].ub) join_tp = JoinDesc; if (!st.empty() && join_tp != None) { // join if (join_tp == nodes[st.back()].tp) { // same type, append to the existing join node add_child(st.back(), v); v = st.back(); st.pop_back(); } else { // different type, create a new join node int u = st.back(); nodes.push_back({join_tp, nodes[u].l, nodes[u].r, nodes[u].lb, nodes[u].ub, {u}}); st.pop_back(); add_child(nodes.size() - 1, v); v = nodes.size() - 1; } } else if (seg.fold(0, i + 1 - (nodes[v].r - nodes[v].l)) == 0) { // cut int l = nodes[v].l, r = nodes[v].r, lb = nodes[v].lb, ub = nodes[v].ub; nodes.push_back({Cut, l, r, lb, ub, {v}}); v = nodes.size() - 1; do { add_child(v, st.back()); st.pop_back(); } while (nodes[v].ub - nodes[v].lb != nodes[v].r - nodes[v].l); std::ranges::reverse(nodes[v].ch); } else { break; } } st.push_back(v); seg.update(0, i + 1, -1); } } private: void add_child(int par, int ch) { nodes[par].ch.push_back(ch); nodes[par].l = std::min(nodes[par].l, nodes[ch].l); nodes[par].r = std::max(nodes[par].r, nodes[ch].r); nodes[par].lb = std::min(nodes[par].lb, nodes[ch].lb); nodes[par].ub = std::max(nodes[par].ub, nodes[ch].ub); } };