test/library_checker/tree/cartesian_tree.test.cpp

• View this file on GitHub
• Last update: 2022-07-19 22:43:05+09:00
• Problem: https://judge.yosupo.jp/problem/cartesian_tree

Depends on

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

Code

#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"
#include <bits/stdc++.h>
using namespace std;
#include "../../../data_structure/other/cartesian_tree_min.hpp"
int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++){
    cin >> a[i];
  }
  vector<int> p = cartesian_tree_min(a);
  for (int i = 0; i < N; i++){
    if (p[i] == -1){
      cout << i;
    } else {
      cout << p[i];
    }
    if (i < N - 1){
      cout << ' ';
    }
  }
  cout << endl;
}

#line 1 "test/library_checker/tree/cartesian_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"
#include <bits/stdc++.h>
using namespace std;
#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;
}
#line 5 "test/library_checker/tree/cartesian_tree.test.cpp"
int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++){
    cin >> a[i];
  }
  vector<int> p = cartesian_tree_min(a);
  for (int i = 0; i < N; i++){
    if (p[i] == -1){
      cout << i;
    } else {
      cout << p[i];
    }
    if (i < N - 1){
      cout << ' ';
    }
  }
  cout << endl;
}

Back to top page