This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/Library
#include "tree/cartesian_tree.hpp"
数列 $a$ を与え、最も小さい要素が根であるCartesian Treeを構築する。返り値の配列 $p$ について、 $p_i$ には親のインデックスが格納されている。根には $-1$ が入っている。 $O(N)$
#pragma once #include <ranges> #include <vector> namespace ebi { template <class T> std::vector<int> cartesian_tree(const std::vector<T> &a) { int n = a.size(); std::vector<int> par(n, -1); std::vector<int> stack; stack.reserve(n); for (int i : std::views::iota(0, n)) { int prev = -1; while (!stack.empty() && a[i] < a[stack.back()]) { prev = stack.back(); stack.pop_back(); } if (prev != -1) { par[prev] = i; } if (!stack.empty()) { par[i] = stack.back(); } stack.push_back(i); } return par; } } // namespace ebi
#line 2 "tree/cartesian_tree.hpp" #include <ranges> #include <vector> namespace ebi { template <class T> std::vector<int> cartesian_tree(const std::vector<T> &a) { int n = a.size(); std::vector<int> par(n, -1); std::vector<int> stack; stack.reserve(n); for (int i : std::views::iota(0, n)) { int prev = -1; while (!stack.empty() && a[i] < a[stack.back()]) { prev = stack.back(); stack.pop_back(); } if (prev != -1) { par[prev] = i; } if (!stack.empty()) { par[i] = stack.back(); } stack.push_back(i); } return par; } } // namespace ebi