test/src/datastructure/cartesian_tree/cartesian_tree.test.cpp

• View this file on GitHub
• Last update: 2023-07-09 04:04:16+09:00
• Problem: https://judge.yosupo.jp/problem/cartesian_tree

Depends on

• Cartesian Tree (library/datastructure/cartesian_tree.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"

#include <iostream>

#include "library/datastructure/cartesian_tree.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int &e : a) std::cin >> e;
    suisen::MinCartesianTreeBuilder t(a);
    for (int i = 0; i < n; ++i) {
        int p = t.parent(i);
        std::cout << (p < 0 ? i : p) << " \n"[i == n - 1];
    }
    return 0;
}

#line 1 "test/src/datastructure/cartesian_tree/cartesian_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"

#include <iostream>

#line 1 "library/datastructure/cartesian_tree.hpp"



#include <array>
#include <cassert>
#include <functional>
#include <vector>

namespace suisen {
    struct CartesianTree : public std::vector<std::array<int, 2>> {
        using base_type = std::vector<std::array<int, 2>>;

        static constexpr int absent = -1;

        const int root;

        CartesianTree() : base_type(), root(0) {}
        CartesianTree(int root, const base_type& g) : base_type(g), root(root) {}
        CartesianTree(int root, base_type&& g) : base_type(std::move(g)), root(root) {}

        auto ranges() const {
            std::vector<std::pair<int, int>> res;
            res.reserve(size());
            auto rec = [&](auto rec, int l, int m, int r) -> void {
                if (m == absent) return;
                const auto& [lm, rm] = (*this)[m];
                rec(rec, l, lm, m), res.emplace_back(l, r), rec(rec, m + 1, rm, r);
            };
            rec(rec, 0, root, size());
            return res;
        }
    };

    template <typename Comparator>
    struct CartesianTreeBuilder {
        CartesianTreeBuilder() = default;
        template <typename RandomAccessibleContainer>
        CartesianTreeBuilder(const RandomAccessibleContainer& a, Comparator comp = Comparator{}) : n(a.size()), comp(comp), par(calc_par(a, comp)) {}

        CartesianTree build() const {
            int root = -1;
            std::vector<std::array<int, 2>> g(n, { CartesianTree::absent, CartesianTree::absent });
            for (int i = 0; i < n; ++i) {
                int p = par[i];
                (p >= 0 ? g[p][p <= i] : root) = i;
            }
            return CartesianTree{ root, std::move(g) };
        }

        template <typename RandomAccessibleContainer>
        static CartesianTree build(const RandomAccessibleContainer& a, Comparator comp = Comparator{}) {
            return CartesianTreeBuilder(a, comp).build();
        }

        int parent(std::size_t i) const {
            assert(i < std::size_t(n));
            return par[i];
        }
        int operator[](std::size_t i) const {
            return parent(i);
        }
    private:
        const int n;
        const Comparator comp;
        const std::vector<int> par;

        template <typename RandomAccessibleContainer>
        static std::vector<int> calc_par(const RandomAccessibleContainer& a, Comparator comp) {
            const int n = a.size();
            std::vector<int> par(n, -1);
            for (int i = 1; i < n; ++i) {
                int p = i - 1, l = i;
                while (p >= 0 and comp(a[i], a[p])) l = p, p = par[p];
                par[l] = i, par[i] = p;
            }
            return par;
        }
    };

    using MinCartesianTreeBuilder = CartesianTreeBuilder<std::less<>>;
    using MaxCartesianTreeBuilder = CartesianTreeBuilder<std::greater<>>;
} // namespace suisen


#line 6 "test/src/datastructure/cartesian_tree/cartesian_tree.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int &e : a) std::cin >> e;
    suisen::MinCartesianTreeBuilder t(a);
    for (int i = 0; i < n; ++i) {
        int p = t.parent(i);
        std::cout << (p < 0 ? i : p) << " \n"[i == n - 1];
    }
    return 0;
}

Back to top page