-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcartesian_tree.cpp
More file actions
50 lines (45 loc) · 1.02 KB
/
cartesian_tree.cpp
File metadata and controls
50 lines (45 loc) · 1.02 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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);
}