This documentation is automatically generated by online-judge-tools/verification-helper
#include "datastructure/cartesian_tree.hpp"
cartesian_tree(a)
: 数列 $\mathrm a$ から誘導される Cartesian Tree を求める。p[i]
は頂点 i
の親を表す。ただし、根である頂点 r
については p[r] = r
。#pragma once
#include <numeric>
#include <optional>
#include <stack>
#include <vector>
template <typename T>
std::vector<int> cartesian_tree(std::vector<T> &a) {
int n = int(a.size());
std::vector<int> p(n);
std::iota(p.begin(), p.end(), 0);
std::stack<int> st;
for (int i = 0; i < n; i++) {
std::optional<int> pre = std::nullopt;
while (!st.empty() && a[i] < a[st.top()]) {
pre = st.top();
st.pop();
}
if (pre) p[pre.value()] = i;
if (!st.empty()) p[i] = st.top();
st.push(i);
}
return p;
}
#line 2 "datastructure/cartesian_tree.hpp"
#include <numeric>
#include <optional>
#include <stack>
#include <vector>
template <typename T>
std::vector<int> cartesian_tree(std::vector<T> &a) {
int n = int(a.size());
std::vector<int> p(n);
std::iota(p.begin(), p.end(), 0);
std::stack<int> st;
for (int i = 0; i < n; i++) {
std::optional<int> pre = std::nullopt;
while (!st.empty() && a[i] < a[st.top()]) {
pre = st.top();
st.pop();
}
if (pre) p[pre.value()] = i;
if (!st.empty()) p[i] = st.top();
st.push(i);
}
return p;
}