Cartesian tree
(tree/cartesian_tree.hpp)

• View this file on GitHub
• Last update: 2021-10-13 23:08:08+09:00
• Include: #include "tree/cartesian_tree.hpp"
• Link: https://judge.yosupo.jp/problem/cartesian_tree

比較可能な要素の列に対し，Cartesian tree を計算．各要素の親となる要素の番号を持った長さ $N$ の std::vector<int> を返す．$O(N)$．デフォルトでは小さい要素がより根に近くなるが，テンプレート引数に std::greater<T> を与えてやることで逆転可能．

使用方法

std::vector<int> A(N);
for (auto &x : Ainv) x = -x;
auto ret = cartesian_tree(A);
auto ret2 = cartesian_tree<int, std::greater<int>>(Ainv);

問題例

• Library Checker: Cartesian Tree
• Codeforces Round #745 (Div. 1) D. Subsequence

Verified with

• tree/test/cartesian_tree.test.cpp

Code

#pragma once
#include <functional>
#include <vector>

// Cartesian tree
// Complexity: O(n)
// By default, the smaller node is nearer to the root
// Return : -1 (root), parent_idx (otherwise)
// Example: [1, 0, 2] => [1, -1, 1]
// Verified: https://judge.yosupo.jp/problem/cartesian_tree
template <class T, class Cmp = std::less<T>>
std::vector<int> cartesian_tree(const std::vector<T> &X) {
    const int n = X.size();
    Cmp comp;
    std::vector<int> st(n);
    int sz = 0;

    std::vector<int> par(n, -1);

    for (int i = 0; i < n; ++i) {
        while (sz >= 2 and comp(X[i], X[st[sz - 1]])) {
            par[st[sz - 1]] = comp(X[i], X[st[sz - 2]]) ? st[sz - 2] : i;
            --sz;
        }
        if (sz == 1 and comp(X[i], X[st[sz - 1]])) par[st[--sz]] = i;
        st[sz++] = i;
    }
    for (; sz > 1; --sz) par[st[sz - 1]] = st[sz - 2];
    return par;
};

#line 2 "tree/cartesian_tree.hpp"
#include <functional>
#include <vector>

// Cartesian tree
// Complexity: O(n)
// By default, the smaller node is nearer to the root
// Return : -1 (root), parent_idx (otherwise)
// Example: [1, 0, 2] => [1, -1, 1]
// Verified: https://judge.yosupo.jp/problem/cartesian_tree
template <class T, class Cmp = std::less<T>>
std::vector<int> cartesian_tree(const std::vector<T> &X) {
    const int n = X.size();
    Cmp comp;
    std::vector<int> st(n);
    int sz = 0;

    std::vector<int> par(n, -1);

    for (int i = 0; i < n; ++i) {
        while (sz >= 2 and comp(X[i], X[st[sz - 1]])) {
            par[st[sz - 1]] = comp(X[i], X[st[sz - 2]]) ? st[sz - 2] : i;
            --sz;
        }
        if (sz == 1 and comp(X[i], X[st[sz - 1]])) par[st[--sz]] = i;
        st[sz++] = i;
    }
    for (; sz > 1; --sz) par[st[sz - 1]] = st[sz - 2];
    return par;
};

Back to top page