sotanishy's competitive programming library

sotanishy's code snippets for competitive programming

View the Project on GitHub sotanishy/cp-library-cpp

:heavy_check_mark: Permutation Tree
(tree/permutation_tree.hpp)

Description

Permutation tree は，順列の区間のマージ過程を表す木である．$\max_{l\leq i < r} p_i - \min_{l\leq i < r} p_i = r - l$ となるような区間の数え上げなどに使える．

Operations

Reference

Depends on

Verified with

Code

#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);
    }
};
Back to top page