test/tree/cartesian_tree.test.cpp

View this file on GitHub
Last update: 2026-03-17 14:01:27+09:00
Problem: https://judge.yosupo.jp/problem/cartesian_tree

Depends on

Cartesian Tree (tree/cartesian_tree.hpp)

Code

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

#include "tree/cartesian_tree.hpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N;
    std::cin >> N;
    std::vector<int> A(N);
    copy_n(std::istream_iterator<int>(std::cin), N, A.begin());
    auto parent = cartesian_tree(A);
    for (auto i = 0; i < N; ++i) {
        std::cout << (~parent[i] ? parent[i] : i) << " ";
    }
}

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

#line 1 "tree/cartesian_tree.hpp"



#include <vector>

std::vector<int> cartesian_tree(const std::vector<int> &a) {
    const auto n = int(a.size());
    std::vector<int> parent(n, -1), st;
    for (auto i = 0; i < n; ++i) {
        auto v = -1;
        while (!st.empty() && a[i] < a[st.back()]) {
            v = st.back();
            st.pop_back();
        }
        if (!st.empty()) {
            parent[i] = st.back();
        }
        if (~v) {
            parent[v] = i;
        }
        st.push_back(i);
    }
    return parent;
}


#line 4 "test/tree/cartesian_tree.test.cpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N;
    std::cin >> N;
    std::vector<int> A(N);
    copy_n(std::istream_iterator<int>(std::cin), N, A.begin());
    auto parent = cartesian_tree(A);
    for (auto i = 0; i < N; ++i) {
        std::cout << (~parent[i] ? parent[i] : i) << " ";
    }
}