test/library-checker/Tree/CartesianTree.test.cpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Problem: https://judge.yosupo.jp/problem/cartesian_tree

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"
#include <bits/stdc++.h>

#include "library/tree/CartesianTree.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> v(n);
    for (int i = 0; i < n; i++)
        std::cin >> v[i];

    auto T = cartesian_tree(v);
    for (int i = 0; i < n; i++)
        std::cout << (i == T.root ? i : T.parent(i).to) << "\n "[i + 1 < n];
}

#line 1 "test/library-checker/Tree/CartesianTree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"
#include <bits/stdc++.h>

#line 4 "library/tree/CartesianTree.hpp"

#line 2 "library/graph/WeightedGraph.hpp"
template <typename T> struct WeightedEdge {
    WeightedEdge() = default;
    WeightedEdge(int from, int to, T weight)
        : from(from), to(to), weight(weight) {}
    int from, to;
    T weight;
    operator int() const { return to; }
};

template <typename T> struct WeightedGraph {
    int n;
    using weight_type = T;
    using edge_type = WeightedEdge<T>;
    std::vector<edge_type> edges;

  protected:
    std::vector<int> in_deg;
    bool prepared;
    class OutgoingEdges {
        WeightedGraph *g;
        int l, r;

      public:
        OutgoingEdges(WeightedGraph *g, int l, int r) : g(g), l(l), r(r) {}
        edge_type *begin() { return &(g->edges[l]); }
        edge_type *end() { return &(g->edges[r]); }
        edge_type &operator[](int i) { return g->edges[l + i]; }
        int size() const { return r - l; }
    };
    class ConstOutgoingEdges {
        const WeightedGraph *g;
        int l, r;

      public:
        ConstOutgoingEdges(const WeightedGraph *g, int l, int r)
            : g(g), l(l), r(r) {}
        const edge_type *begin() const { return &(g->edges[l]); }
        const edge_type *end() const { return &(g->edges[r]); }
        const edge_type &operator[](int i) const { return g->edges[l + i]; }
        int size() const { return r - l; }
    };

  public:
    OutgoingEdges operator[](int v) {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }
    const ConstOutgoingEdges operator[](int v) const {
        assert(prepared);
        return {this, in_deg[v], in_deg[v + 1]};
    }

    bool is_prepared() const { return prepared; }

    WeightedGraph() : n(0), in_deg(1, 0), prepared(false) {}
    WeightedGraph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
    WeightedGraph(int n, int m, bool directed = false, int indexed = 1)
        : n(n), in_deg(n + 1, 0), prepared(false) {
        scan(m, directed, indexed);
    }

    void resize(int n) { n = n; }

    void add_arc(int from, int to, T weight) {
        assert(!prepared);
        assert(0 <= from and from < n and 0 <= to and to < n);
        edges.emplace_back(from, to, weight);
        in_deg[from + 1]++;
    }
    void add_edge(int u, int v, T weight) {
        add_arc(u, v, weight);
        add_arc(v, u, weight);
    }
    void add_arc(const edge_type &e) { add_arc(e.from, e.to, e.weight); }
    void add_edge(const edge_type &e) { add_edge(e.from, e.to, e.weight); }

    void scan(int m, bool directed = false, int indexed = 1) {
        edges.reserve(directed ? m : 2 * m);
        while (m--) {
            int u, v;
            std::cin >> u >> v;
            u -= indexed;
            v -= indexed;
            T weight;
            std::cin >> weight;
            if (directed)
                add_arc(u, v, weight);
            else
                add_edge(u, v, weight);
        }
        build();
    }

    void build() {
        assert(!prepared);
        prepared = true;
        for (int v = 0; v < n; v++)
            in_deg[v + 1] += in_deg[v];
        std::vector<edge_type> new_edges(in_deg.back());
        auto counter = in_deg;
        for (auto &&e : edges)
            new_edges[counter[e.from]++] = e;
        edges = new_edges;
    }

    void graph_debug() const {
#ifndef __DEBUG
        return;
#endif
        assert(prepared);
        for (int from = 0; from < n; from++) {
            std::cerr << from << ";";
            for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
                std::cerr << "(" << edges[i].to << "," << edges[i].weight
                          << ")";
            std::cerr << "\n";
        }
    }
};
#line 3 "library/tree/WeightedTree.hpp"
template <typename T> struct WeightedTree : WeightedGraph<T> {
    using WeightedGraph<T>::WeightedGraph;
    using edge_type = typename WeightedGraph<T>::edge_type;
    using OutgoingEdges = typename WeightedGraph<T>::OutgoingEdges;
    using WeightedGraph<T>::n;
    using WeightedGraph<T>::in_deg;

    int root = -1;
    std::vector<int> DFS, BFS, depth;

    void scan_root(int indexed = 1) {
        for (int i = 1; i < n; i++) {
            int p;
            std::cin >> p;
            T weight;
            std::cin >> weight;
            add_edge(p - indexed, i, weight);
        }
        build();
    }
    void scan(int indexed = 1) {
        WeightedGraph<T>::scan(n - 1, false, indexed);
        build();
    }

    edge_type &parent(int v) {
        assert(~root and root != v);
        return (*this)[v][0];
    }
    OutgoingEdges son(int v) {
        assert(~root);
        if (v == root)
            return {this, in_deg[v], in_deg[v + 1]};
        return {this, in_deg[v] + 1, in_deg[v + 1]};
    }

  private:
    void dfs(int v, int pre = -1) {
        for (auto &e : (*this)[v]) {
            if (e.to == pre)
                std::swap((*this)[v][0], e);
            else {
                depth[e.to] = depth[v] + 1;
                dfs(e.to, v);
            }
        }
        DFS.push_back(v);
    }

  public:
    void build(int r = 0) {
        if (!WeightedGraph<T>::is_prepared())
            WeightedGraph<T>::build();
        if (~root) {
            assert(r == root);
            return;
        }
        root = r;
        depth = std::vector<int>(n, 0);
        DFS.reserve(n);
        BFS.reserve(n);
        dfs(root);
        std::queue<int> que;
        que.push(root);
        while (que.size()) {
            int p = que.front();
            que.pop();
            BFS.push_back(p);
            for (const auto &e : son(p))
                que.push(e.to);
        }
    }
};
#line 6 "library/tree/CartesianTree.hpp"

// 最小値で分割 根付き木を渡す 根が最小値のindex
// 等しい値に関しては index の大小を比較する
// 辺の重みは子の部分木が担当する半開区間
template <typename T>
WeightedTree<std::pair<int, int>> cartesian_tree(const std::vector<T> &v) {
    int n = v.size();
    std::vector<std::pair<int, int>> lr(n, {0, n});
    std::stack<int> sta;
    for (int i = 0; i < n; i++) {
        while (sta.size() and v[i] < v[sta.top()]) {
            lr[sta.top()].second = i;
            sta.pop();
        }
        if (sta.size())
            lr[i].first = sta.top() + 1;
        sta.push(i);
    }
    WeightedTree<std::pair<int, int>> t(n);
    int root;
    for (int i = 0; i < n; i++) {
        const auto &[l, r] = lr[i];
        if (l == 0 and r == n)
            root = i;
        else {
            if (l == 0)
                t.add_edge(r, i, lr[i]);
            if (r == n)
                t.add_edge(l - 1, i, lr[i]);
            if (l != 0 and r != n)
                if (v[l - 1] > v[r])
                    t.add_edge(l - 1, i, lr[i]);
                else
                    t.add_edge(r, i, lr[i]);
        }
    }
    t.build(root);
    return t;
}
#line 5 "test/library-checker/Tree/CartesianTree.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> v(n);
    for (int i = 0; i < n; i++)
        std::cin >> v[i];

    auto T = cartesian_tree(v);
    for (int i = 0; i < n; i++)
        std::cout << (i == T.root ? i : T.parent(i).to) << "\n "[i + 1 < n];
}