verifying_test/yosupo/tree/cartesian_tree.test.cpp

View this file on GitHub
Last update: 2022-01-28 02:17:51+09:00
Problem: https://judge.yosupo.jp/problem/cartesian_tree

Depends on

Code

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

#include <cstdio>
#include <queue>
#include <cassert>
#include "../../../algorithm/cartesian_tree.cpp"

int main() {
    int N; scanf("%d", &N);

    vector<int> A(N);
    for(auto &e : A) scanf("%d", &e);

    auto [G, root] = getCartesianTree(A);
    vector<bool> visited(N);
    vector<int> ans(N, root);
    queue<int> que;
    que.emplace(root);
    visited[root] = true;
    while(que.size()) {
        int u = que.front(); que.pop();
        for(auto e : G[u]) {
            int v = e.to;
            assert(!visited[v]);
            ans[v] = u;
            visited[v] = true;
            que.emplace(v);
        }
    }

    for(int i=0; i<N; i++) printf("%d%c", ans[i], " \n"[i + 1 == N]);
    return 0;
}

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

#include <cstdio>
#include <queue>
#include <cassert>
#line 2 "algorithm/cartesian_tree.cpp"

/**
 * @brief Cartesian Tree
 * @docs docs/algorithm/cartesian_tree.md
 */

#include <vector>
#include <stack>
#include <utility>
#include <functional>
using namespace std;

#line 1 "graph/graph_000_basic.cpp"
// 移動元と行先と辺のコストを記録する構造体

template <typename T = int>
struct Edge {
    int from, to;
    T cost;
    Edge(int s, T d = 1) : to(s), cost(d) {}
    Edge(int f, int s, T d) : from(f), to(s), cost(d) {}

    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    bool operator>(const Edge &e) const {
        return cost > e.cost;
    }
};

template <typename T = int>
using Graph = vector< vector< Edge<T> > >;
#line 15 "algorithm/cartesian_tree.cpp"

template <typename Tp = int>
pair< Graph<>, int > getCartesianTree(const vector<Tp> &A,
    function<bool(Tp, Tp)> cmp = [](Tp a, Tp b) {
        return a < b; // min
    }
) {
    int N = A.size();
    vector<int> par(N, -1), st;
    st.reserve(N);
    for(int i=0; i<N; i++) {
        int prev_idx = -1;
        while(st.size() and cmp(A[i], A[st.back()])) {
            prev_idx = st.back(); st.pop_back();
        }
        if(prev_idx >= 0) {
            par[ prev_idx ] = i;
        }
        if(st.size()) {
            par[i] = st.back();
        }
        st.emplace_back(i);
    }

    int root = -1;
    Graph<> G(N);
    for(int i=0; i<N; i++) {
        if(par[i] < 0) {
            root = i;
        }
        else {
            G[ par[i] ].emplace_back(i);
        }
    }
    return make_pair(G, root);
}
#line 7 "verifying_test/yosupo/tree/cartesian_tree.test.cpp"

int main() {
    int N; scanf("%d", &N);

    vector<int> A(N);
    for(auto &e : A) scanf("%d", &e);

    auto [G, root] = getCartesianTree(A);
    vector<bool> visited(N);
    vector<int> ans(N, root);
    queue<int> que;
    que.emplace(root);
    visited[root] = true;
    while(que.size()) {
        int u = que.front(); que.pop();
        for(auto e : G[u]) {
            int v = e.to;
            assert(!visited[v]);
            ans[v] = u;
            visited[v] = true;
            que.emplace(v);
        }
    }

    for(int i=0; i<N; i++) printf("%d%c", ans[i], " \n"[i + 1 == N]);
    return 0;
}