This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
see: https://kmyk.github.io/blog/blog/2020/07/27/recursion-on-cartesian-tree/
getCartesianTree(A, cmp)
: $O(N)$
true
)#pragma once
/**
* @brief Cartesian Tree
* @docs docs/algorithm/cartesian_tree.md
*/
#include <vector>
#include <stack>
#include <utility>
#include <functional>
using namespace std;
#include "../graph/graph_000_basic.cpp"
template <typename Tp = int>
pair< Graph<>, int > getCartesianTree(const vector<Tp> &A,
function<bool(Tp, Tp)> cmp = [](Tp a, Tp b) {
return a < b; // min
}
) {
int N = A.size();
vector<int> par(N, -1), st;
st.reserve(N);
for(int i=0; i<N; i++) {
int prev_idx = -1;
while(st.size() and cmp(A[i], A[st.back()])) {
prev_idx = st.back(); st.pop_back();
}
if(prev_idx >= 0) {
par[ prev_idx ] = i;
}
if(st.size()) {
par[i] = st.back();
}
st.emplace_back(i);
}
int root = -1;
Graph<> G(N);
for(int i=0; i<N; i++) {
if(par[i] < 0) {
root = i;
}
else {
G[ par[i] ].emplace_back(i);
}
}
return make_pair(G, root);
}
#line 2 "algorithm/cartesian_tree.cpp"
/**
* @brief Cartesian Tree
* @docs docs/algorithm/cartesian_tree.md
*/
#include <vector>
#include <stack>
#include <utility>
#include <functional>
using namespace std;
#line 1 "graph/graph_000_basic.cpp"
// 移動元と行先と辺のコストを記録する構造体
template <typename T = int>
struct Edge {
int from, to;
T cost;
Edge(int s, T d = 1) : to(s), cost(d) {}
Edge(int f, int s, T d) : from(f), to(s), cost(d) {}
bool operator<(const Edge &e) const {
return cost < e.cost;
}
bool operator>(const Edge &e) const {
return cost > e.cost;
}
};
template <typename T = int>
using Graph = vector< vector< Edge<T> > >;
#line 15 "algorithm/cartesian_tree.cpp"
template <typename Tp = int>
pair< Graph<>, int > getCartesianTree(const vector<Tp> &A,
function<bool(Tp, Tp)> cmp = [](Tp a, Tp b) {
return a < b; // min
}
) {
int N = A.size();
vector<int> par(N, -1), st;
st.reserve(N);
for(int i=0; i<N; i++) {
int prev_idx = -1;
while(st.size() and cmp(A[i], A[st.back()])) {
prev_idx = st.back(); st.pop_back();
}
if(prev_idx >= 0) {
par[ prev_idx ] = i;
}
if(st.size()) {
par[i] = st.back();
}
st.emplace_back(i);
}
int root = -1;
Graph<> G(N);
for(int i=0; i<N; i++) {
if(par[i] < 0) {
root = i;
}
else {
G[ par[i] ].emplace_back(i);
}
}
return make_pair(G, root);
}