Cartesian Tree
(datastructure/cartesian_tree.hpp)

• View this file on GitHub
• Last update: 2023-03-05 19:05:08+09:00
• Include: #include "datastructure/cartesian_tree.hpp"

使い方

• cartesian_tree(a): 数列 $\mathrm a$ から誘導される Cartesian Tree を求める。p[i] は頂点 i の親を表す。ただし、根である頂点 r については p[r] = r。

Verified with

• test/library-checker/cartesian_tree.test.cpp

Code

#pragma once
#include <numeric>
#include <optional>
#include <stack>
#include <vector>
template <typename T>
std::vector<int> cartesian_tree(std::vector<T> &a) {
    int n = int(a.size());
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    std::stack<int> st;
    for (int i = 0; i < n; i++) {
        std::optional<int> pre = std::nullopt;
        while (!st.empty() && a[i] < a[st.top()]) {
            pre = st.top();
            st.pop();
        }
        if (pre) p[pre.value()] = i;
        if (!st.empty()) p[i] = st.top();
        st.push(i);
    }
    return p;
}

#line 2 "datastructure/cartesian_tree.hpp"
#include <numeric>
#include <optional>
#include <stack>
#include <vector>
template <typename T>
std::vector<int> cartesian_tree(std::vector<T> &a) {
    int n = int(a.size());
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    std::stack<int> st;
    for (int i = 0; i < n; i++) {
        std::optional<int> pre = std::nullopt;
        while (!st.empty() && a[i] < a[st.top()]) {
            pre = st.top();
            st.pop();
        }
        if (pre) p[pre.value()] = i;
        if (!st.empty()) p[i] = st.top();
        st.push(i);
    }
    return p;
}

Back to top page