tests/cartesian_tree/parent.test.cpp

• View this file on GitHub
• Last update: 2025-01-22 03:51:11+00:00
• Problem: https://judge.yosupo.jp/problem/cartesian_tree

Depends on

• Cartesian tree (tools/cartesian_tree.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/cartesian_tree

#include <iostream>
#include <vector>
#include <functional>
#include <limits>
#include <cstddef>
#include "tools/cartesian_tree.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int N;
  std::cin >> N;
  std::vector<int> a(N);
  for (auto& a_i : a) std::cin >> a_i;

  const tools::cartesian_tree<int> cartesian_tree(a);
  for (int i = 0; i < N; ++i) {
    if (i) std::cout << ' ';
    auto p = cartesian_tree.get_vertex(i).parent;
    if (p == std::numeric_limits<std::size_t>::max()) p = i;
    std::cout << p;
  }
  std::cout << '\n';

  return 0;
}

#line 1 "tests/cartesian_tree/parent.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/cartesian_tree

#include <iostream>
#include <vector>
#include <functional>
#include <limits>
#include <cstddef>
#line 1 "tools/cartesian_tree.hpp"



#line 6 "tools/cartesian_tree.hpp"
#include <utility>
#line 9 "tools/cartesian_tree.hpp"
#include <stack>
#include <cassert>

namespace tools {
  template <typename T, typename Compare = ::std::less<T>>
  class cartesian_tree {
  public:
    struct vertex {
      ::std::size_t parent;
      ::std::size_t left;
      ::std::size_t right;
      ::std::pair<::std::size_t, ::std::size_t> interval;
    };

  private:
    Compare m_comp;
    ::std::vector<vertex> m_vertices;

  public:
    cartesian_tree() = default;
    cartesian_tree(const ::tools::cartesian_tree<T, Compare>&) = default;
    cartesian_tree(::tools::cartesian_tree<T, Compare>&&) = default;
    ~cartesian_tree() = default;
    ::tools::cartesian_tree<T, Compare>& operator=(const ::tools::cartesian_tree<T, Compare>&) = default;
    ::tools::cartesian_tree<T, Compare>& operator=(::tools::cartesian_tree<T, Compare>&&) = default;

    explicit cartesian_tree(const ::std::vector<T>& a, const Compare& comp = Compare()) : m_comp(comp), m_vertices(a.size()) {
      const auto NONE = ::std::numeric_limits<::std::size_t>::max();

      for (::std::size_t i = 0; i < a.size(); ++i) {
        this->m_vertices[i].parent = i ? i - 1 : NONE;
        this->m_vertices[i].left = NONE;
        this->m_vertices[i].right = NONE;
        auto c = NONE;
        while (this->m_vertices[i].parent != NONE && this->m_comp(a[i], a[this->m_vertices[i].parent])) {
          if (c != NONE) {
            this->m_vertices[c].parent = this->m_vertices[i].parent;
          }
          c = this->m_vertices[i].parent;

          const auto gp = this->m_vertices[this->m_vertices[i].parent].parent;
          this->m_vertices[this->m_vertices[i].parent].parent = i;
          this->m_vertices[i].parent = gp;
        }
      }

      auto root = NONE;
      for (::std::size_t i = 0; i < a.size(); ++i) {
        const auto p = this->m_vertices[i].parent;
        if (p == NONE) {
          root = i;
        } else {
          if (p < i) {
            this->m_vertices[p].right= i;
          } else {
            this->m_vertices[p].left = i;
          }
        }
      }

      ::std::vector<::std::size_t> strict_left(a.size());
      strict_left[root] = 0;
      this->m_vertices[root].interval = ::std::make_pair(0, a.size());
      ::std::stack<::std::size_t> stack;
      stack.push(root);
      while (!stack.empty()) {
        const auto here = stack.top();
        stack.pop();
        const auto& v = this->m_vertices[here];
        if (v.right != NONE) {
          strict_left[v.right] = here + 1;
          this->m_vertices[v.right].interval = ::std::make_pair(
            this->m_comp(a[here], a[v.right]) ? strict_left[v.right] : this->m_vertices[here].interval.first,
            this->m_vertices[here].interval.second
          );
          stack.push(v.right);
        }
        if (v.left != NONE) {
          strict_left[v.left] = strict_left[here];
          this->m_vertices[v.left].interval = ::std::make_pair(strict_left[v.left], here);
          stack.push(v.left);
        }
      }
    }
    template <typename InputIterator>
    cartesian_tree(const InputIterator begin, const InputIterator end, const Compare& comp = Compare()) : cartesian_tree(::std::vector<T>(begin, end), comp) {
    }

    ::std::size_t size() const {
      return this->m_vertices.size();
    }
    const vertex& get_vertex(::std::size_t i) const {
      assert(i < this->size());
      return this->m_vertices[i];
    }
    const ::std::vector<vertex>& vertices() const {
      return this->m_vertices;
    }
  };
}


#line 9 "tests/cartesian_tree/parent.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int N;
  std::cin >> N;
  std::vector<int> a(N);
  for (auto& a_i : a) std::cin >> a_i;

  const tools::cartesian_tree<int> cartesian_tree(a);
  for (int i = 0; i < N; ++i) {
    if (i) std::cout << ' ';
    auto p = cartesian_tree.get_vertex(i).parent;
    if (p == std::numeric_limits<std::size_t>::max()) p = i;
    std::cout << p;
  }
  std::cout << '\n';

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	almost-decreasing_00	AC	115 ms	54 MB
g++	almost-decreasing_01	AC	57 ms	27 MB
g++	almost-increasing_00	AC	112 ms	54 MB
g++	almost-increasing_01	AC	56 ms	27 MB
g++	decreasing_00	AC	125 ms	54 MB
g++	decreasing_01	AC	60 ms	27 MB
g++	example_00	AC	6 ms	4 MB
g++	example_01	AC	5 ms	4 MB
g++	increasing_00	AC	112 ms	54 MB
g++	increasing_01	AC	56 ms	27 MB
g++	random_00	AC	133 ms	54 MB
g++	random_01	AC	69 ms	27 MB
g++	random_02	AC	84 ms	33 MB
g++	random_03	AC	60 ms	25 MB
g++	random_04	AC	107 ms	44 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	4 ms	4 MB
g++	small_03	AC	4 ms	4 MB
g++	small_04	AC	4 ms	4 MB
g++	small_05	AC	4 ms	4 MB
g++	small_06	AC	4 ms	4 MB
g++	small_07	AC	4 ms	4 MB
g++	small_08	AC	4 ms	4 MB
g++	small_09	AC	4 ms	4 MB

Back to top page