This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub kmyk/competitive-programming-library
#include "graph/cartesian_tree.hpp"
#pragma once
#include <functional>
#include <vector>
#include "../utils/macros.hpp"
/**
* @brief Cartesian tree ($O(n)$)
* @note the smallest value is the root
* @note if a is not distinct, the way for tie-break is undefined
* @return the binary tree as the list of parents
*/
template <class T, class Comparator = std::less<int> >
std::vector<int> construct_cartesian_tree(const std::vector<T> & a, const Comparator & cmp = Comparator()) {
int n = a.size();
std::vector<int> parent(n, -1);
REP3 (i, 1, n) {
int p = i - 1; // parent of i
int l = -1; // left child of i
while (p != -1 and cmp(a[i], a[p])) {
int pp = parent[p]; // parent of parent of i
if (l != -1) {
parent[l] = p;
}
parent[p] = i;
l = p;
p = pp;
}
parent[i] = p;
}
return parent;
}
#line 2 "graph/cartesian_tree.hpp"
#include <functional>
#include <vector>
#line 2 "utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 5 "graph/cartesian_tree.hpp"
/**
* @brief Cartesian tree ($O(n)$)
* @note the smallest value is the root
* @note if a is not distinct, the way for tie-break is undefined
* @return the binary tree as the list of parents
*/
template <class T, class Comparator = std::less<int> >
std::vector<int> construct_cartesian_tree(const std::vector<T> & a, const Comparator & cmp = Comparator()) {
int n = a.size();
std::vector<int> parent(n, -1);
REP3 (i, 1, n) {
int p = i - 1; // parent of i
int l = -1; // left child of i
while (p != -1 and cmp(a[i], a[p])) {
int pp = parent[p]; // parent of parent of i
if (l != -1) {
parent[l] = p;
}
parent[p] = i;
l = p;
p = pp;
}
parent[i] = p;
}
return parent;
}