library/tree/CartesianTree.hpp
Depends on
Verified with
Code
#include <stack>
#include <utility>
#include <vector>
#include "library/tree/WeightedTree.hpp"
// 最小値で分割 根付き木を渡す 根が最小値のindex
// 等しい値に関しては index の大小を比較する
// 辺の重みは子の部分木が担当する半開区間
template <typename T>
WeightedTree<std::pair<int, int>> cartesian_tree(const std::vector<T> &v) {
int n = v.size();
std::vector<std::pair<int, int>> lr(n, {0, n});
std::stack<int> sta;
for (int i = 0; i < n; i++) {
while (sta.size() and v[i] < v[sta.top()]) {
lr[sta.top()].second = i;
sta.pop();
}
if (sta.size())
lr[i].first = sta.top() + 1;
sta.push(i);
}
WeightedTree<std::pair<int, int>> t(n);
int root;
for (int i = 0; i < n; i++) {
const auto &[l, r] = lr[i];
if (l == 0 and r == n)
root = i;
else {
if (l == 0)
t.add_edge(r, i, lr[i]);
if (r == n)
t.add_edge(l - 1, i, lr[i]);
if (l != 0 and r != n)
if (v[l - 1] > v[r])
t.add_edge(l - 1, i, lr[i]);
else
t.add_edge(r, i, lr[i]);
}
}
t.build(root);
return t;
}
#line 1 "library/tree/CartesianTree.hpp"
#include <stack>
#include <utility>
#include <vector>
#line 2 "library/graph/WeightedGraph.hpp"
template <typename T> struct WeightedEdge {
WeightedEdge() = default;
WeightedEdge(int from, int to, T weight)
: from(from), to(to), weight(weight) {}
int from, to;
T weight;
operator int() const { return to; }
};
template <typename T> struct WeightedGraph {
int n;
using weight_type = T;
using edge_type = WeightedEdge<T>;
std::vector<edge_type> edges;
protected:
std::vector<int> in_deg;
bool prepared;
class OutgoingEdges {
WeightedGraph *g;
int l, r;
public:
OutgoingEdges(WeightedGraph *g, int l, int r) : g(g), l(l), r(r) {}
edge_type *begin() { return &(g->edges[l]); }
edge_type *end() { return &(g->edges[r]); }
edge_type &operator[](int i) { return g->edges[l + i]; }
int size() const { return r - l; }
};
class ConstOutgoingEdges {
const WeightedGraph *g;
int l, r;
public:
ConstOutgoingEdges(const WeightedGraph *g, int l, int r)
: g(g), l(l), r(r) {}
const edge_type *begin() const { return &(g->edges[l]); }
const edge_type *end() const { return &(g->edges[r]); }
const edge_type &operator[](int i) const { return g->edges[l + i]; }
int size() const { return r - l; }
};
public:
OutgoingEdges operator[](int v) {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
const ConstOutgoingEdges operator[](int v) const {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
bool is_prepared() const { return prepared; }
WeightedGraph() : n(0), in_deg(1, 0), prepared(false) {}
WeightedGraph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
WeightedGraph(int n, int m, bool directed = false, int indexed = 1)
: n(n), in_deg(n + 1, 0), prepared(false) {
scan(m, directed, indexed);
}
void resize(int n) { n = n; }
void add_arc(int from, int to, T weight) {
assert(!prepared);
assert(0 <= from and from < n and 0 <= to and to < n);
edges.emplace_back(from, to, weight);
in_deg[from + 1]++;
}
void add_edge(int u, int v, T weight) {
add_arc(u, v, weight);
add_arc(v, u, weight);
}
void add_arc(const edge_type &e) { add_arc(e.from, e.to, e.weight); }
void add_edge(const edge_type &e) { add_edge(e.from, e.to, e.weight); }
void scan(int m, bool directed = false, int indexed = 1) {
edges.reserve(directed ? m : 2 * m);
while (m--) {
int u, v;
std::cin >> u >> v;
u -= indexed;
v -= indexed;
T weight;
std::cin >> weight;
if (directed)
add_arc(u, v, weight);
else
add_edge(u, v, weight);
}
build();
}
void build() {
assert(!prepared);
prepared = true;
for (int v = 0; v < n; v++)
in_deg[v + 1] += in_deg[v];
std::vector<edge_type> new_edges(in_deg.back());
auto counter = in_deg;
for (auto &&e : edges)
new_edges[counter[e.from]++] = e;
edges = new_edges;
}
void graph_debug() const {
#ifndef __DEBUG
return;
#endif
assert(prepared);
for (int from = 0; from < n; from++) {
std::cerr << from << ";";
for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
std::cerr << "(" << edges[i].to << "," << edges[i].weight
<< ")";
std::cerr << "\n";
}
}
};
#line 3 "library/tree/WeightedTree.hpp"
template <typename T> struct WeightedTree : WeightedGraph<T> {
using WeightedGraph<T>::WeightedGraph;
using edge_type = typename WeightedGraph<T>::edge_type;
using OutgoingEdges = typename WeightedGraph<T>::OutgoingEdges;
using WeightedGraph<T>::n;
using WeightedGraph<T>::in_deg;
int root = -1;
std::vector<int> DFS, BFS, depth;
void scan_root(int indexed = 1) {
for (int i = 1; i < n; i++) {
int p;
std::cin >> p;
T weight;
std::cin >> weight;
add_edge(p - indexed, i, weight);
}
build();
}
void scan(int indexed = 1) {
WeightedGraph<T>::scan(n - 1, false, indexed);
build();
}
edge_type &parent(int v) {
assert(~root and root != v);
return (*this)[v][0];
}
OutgoingEdges son(int v) {
assert(~root);
if (v == root)
return {this, in_deg[v], in_deg[v + 1]};
return {this, in_deg[v] + 1, in_deg[v + 1]};
}
private:
void dfs(int v, int pre = -1) {
for (auto &e : (*this)[v]) {
if (e.to == pre)
std::swap((*this)[v][0], e);
else {
depth[e.to] = depth[v] + 1;
dfs(e.to, v);
}
}
DFS.push_back(v);
}
public:
void build(int r = 0) {
if (!WeightedGraph<T>::is_prepared())
WeightedGraph<T>::build();
if (~root) {
assert(r == root);
return;
}
root = r;
depth = std::vector<int>(n, 0);
DFS.reserve(n);
BFS.reserve(n);
dfs(root);
std::queue<int> que;
que.push(root);
while (que.size()) {
int p = que.front();
que.pop();
BFS.push_back(p);
for (const auto &e : son(p))
que.push(e.to);
}
}
};
#line 6 "library/tree/CartesianTree.hpp"
// 最小値で分割 根付き木を渡す 根が最小値のindex
// 等しい値に関しては index の大小を比較する
// 辺の重みは子の部分木が担当する半開区間
template <typename T>
WeightedTree<std::pair<int, int>> cartesian_tree(const std::vector<T> &v) {
int n = v.size();
std::vector<std::pair<int, int>> lr(n, {0, n});
std::stack<int> sta;
for (int i = 0; i < n; i++) {
while (sta.size() and v[i] < v[sta.top()]) {
lr[sta.top()].second = i;
sta.pop();
}
if (sta.size())
lr[i].first = sta.top() + 1;
sta.push(i);
}
WeightedTree<std::pair<int, int>> t(n);
int root;
for (int i = 0; i < n; i++) {
const auto &[l, r] = lr[i];
if (l == 0 and r == n)
root = i;
else {
if (l == 0)
t.add_edge(r, i, lr[i]);
if (r == n)
t.add_edge(l - 1, i, lr[i]);
if (l != 0 and r != n)
if (v[l - 1] > v[r])
t.add_edge(l - 1, i, lr[i]);
else
t.add_edge(r, i, lr[i]);
}
}
t.build(root);
return t;
}
Back to top page
build/pch/stdc++.hpp