Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

:question: Cartesian Tree
(graph/others/cartesian-tree.hpp)

概要

数列に対応する Cartesian tree を求める.

使い方

計算量

Verified with

Code

#pragma once
/**
 * @brief Cartesian Tree
 * @docs docs/cartesian-tree.md
 * @see https://kimiyuki.net/blog/2020/07/27/recursion-on-cartesian-tree/
 */
template< typename T >
vector< int > cartesian_tree(const vector< T > &v) {
  int n = (int) v.size();
  vector< int > par(n, -1);
  stack< int > st;
  for(int i = 0; i < n; i++) {
    int last = -1;
    while(!st.empty() && v[st.top()] >= v[i]) {
      last = st.top();
      st.pop();
    }
    if(!st.empty()) par[i] = st.top();
    if(last >= 0) par[last] = i;
    st.emplace(i);
  }
  return par;
}
#line 2 "graph/others/cartesian-tree.hpp"
/**
 * @brief Cartesian Tree
 * @docs docs/cartesian-tree.md
 * @see https://kimiyuki.net/blog/2020/07/27/recursion-on-cartesian-tree/
 */
template< typename T >
vector< int > cartesian_tree(const vector< T > &v) {
  int n = (int) v.size();
  vector< int > par(n, -1);
  stack< int > st;
  for(int i = 0; i < n; i++) {
    int last = -1;
    while(!st.empty() && v[st.top()] >= v[i]) {
      last = st.top();
      st.pop();
    }
    if(!st.empty()) par[i] = st.top();
    if(last >= 0) par[last] = i;
    st.emplace(i);
  }
  return par;
}
Back to top page