デカルト木
(data_structure/other/cartesian_tree_min.hpp)

• View this file on GitHub
• Last update: 2022-07-17 06:33:45+09:00
• Include: #include "data_structure/other/cartesian_tree_min.hpp"

Verified with

• test/library_checker/tree/cartesian_tree.test.cpp

Code

#pragma once
/**
 * @brief デカルト木
*/
vector<int> cartesian_tree_min(vector<int> &A){
  int N = A.size();
  vector<int> pr(N, -1);
  stack<int> st;
  st.push(0);
  for (int i = 1; i < N; i++){
    int prev = -1;
    while (!st.empty()){
      int j = st.top();
      if (A[i] < A[j]){
        st.pop();
        if (prev != -1){
          pr[prev] = j;
        }
        prev = j;
      } else {
        break;
      }
    }
    if (prev != -1){
      pr[prev] = i;
    }
    st.push(i);
  }
  while (st.size() >= 2){
    int x = st.top();
    st.pop();
    pr[x] = st.top();
  }
  return pr;
}

#line 2 "data_structure/other/cartesian_tree_min.hpp"
/**
 * @brief デカルト木
*/
vector<int> cartesian_tree_min(vector<int> &A){
  int N = A.size();
  vector<int> pr(N, -1);
  stack<int> st;
  st.push(0);
  for (int i = 1; i < N; i++){
    int prev = -1;
    while (!st.empty()){
      int j = st.top();
      if (A[i] < A[j]){
        st.pop();
        if (prev != -1){
          pr[prev] = j;
        }
        prev = j;
      } else {
        break;
      }
    }
    if (prev != -1){
      pr[prev] = i;
    }
    st.push(i);
  }
  while (st.size() >= 2){
    int x = st.top();
    st.pop();
    pr[x] = st.top();
  }
  return pr;
}

Back to top page