This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"
#include <cstdio>
#include <queue>
#include <cassert>
#include "../../../algorithm/cartesian_tree.cpp"
int main() {
int N; scanf("%d", &N);
vector<int> A(N);
for(auto &e : A) scanf("%d", &e);
auto [G, root] = getCartesianTree(A);
vector<bool> visited(N);
vector<int> ans(N, root);
queue<int> que;
que.emplace(root);
visited[root] = true;
while(que.size()) {
int u = que.front(); que.pop();
for(auto e : G[u]) {
int v = e.to;
assert(!visited[v]);
ans[v] = u;
visited[v] = true;
que.emplace(v);
}
}
for(int i=0; i<N; i++) printf("%d%c", ans[i], " \n"[i + 1 == N]);
return 0;
}
#line 1 "verifying_test/yosupo/tree/cartesian_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/cartesian_tree"
#include <cstdio>
#include <queue>
#include <cassert>
#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);
}
#line 7 "verifying_test/yosupo/tree/cartesian_tree.test.cpp"
int main() {
int N; scanf("%d", &N);
vector<int> A(N);
for(auto &e : A) scanf("%d", &e);
auto [G, root] = getCartesianTree(A);
vector<bool> visited(N);
vector<int> ans(N, root);
queue<int> que;
que.emplace(root);
visited[root] = true;
while(que.size()) {
int u = que.front(); que.pop();
for(auto e : G[u]) {
int v = e.to;
assert(!visited[v]);
ans[v] = u;
visited[v] = true;
que.emplace(v);
}
}
for(int i=0; i<N; i++) printf("%d%c", ans[i], " \n"[i + 1 == N]);
return 0;
}