cp-book
ecnerwala's competitive programming library
🧪 cartesian_tree.test.cpp
Depends on
cartesian_tree.hppCode
#include "cartesian_tree.hpp"
#include <catch2/catch_test_macros.hpp>
#include <catch2/catch_get_random_seed.hpp>
#include <bits/stdc++.h>
TEST_CASE("Cartesian Tree", "[cartesian_tree]") {
std::mt19937 mt(Catch::getSeed());
for (int sz : {0, 1, 2, 3, 5, 8, 13}) {
std::vector<int> v(sz);
iota(v.begin(), v.end(), 0);
shuffle(v.begin(), v.end(), mt);
{
CartesianTree t = CartesianTree::build_min_tree(v);
for (int i = 1; i < int(t.size()); i += 2) {
REQUIRE(t[i].m == i/2);
REQUIRE(t[i].l <= t[i].m);
REQUIRE(t[i].m <= t[i].r);
REQUIRE(t[t[i].c[0]].l == t[i].l);
REQUIRE(t[t[i].c[0]].r == t[i].m-1);
REQUIRE(t[t[i].c[1]].l == t[i].m+1);
REQUIRE(t[t[i].c[1]].r == t[i].r);
REQUIRE((t[t[i].c[0]].l > t[t[i].c[0]].r || v[t[i].m] < v[t[t[i].c[0]].m]));
REQUIRE((t[t[i].c[1]].l > t[t[i].c[1]].r || v[t[i].m] < v[t[t[i].c[1]].m]));
}
}
{
CartesianTree t = CartesianTree::build_max_tree(v);
for (int i = 1; i < int(t.size()); i += 2) {
REQUIRE(t[i].m == i/2);
REQUIRE(t[i].l <= t[i].m);
REQUIRE(t[i].m <= t[i].r);
REQUIRE(t[t[i].c[0]].l == t[i].l);
REQUIRE(t[t[i].c[0]].r == t[i].m-1);
REQUIRE(t[t[i].c[1]].l == t[i].m+1);
REQUIRE(t[t[i].c[1]].r == t[i].r);
REQUIRE((t[t[i].c[0]].l > t[t[i].c[0]].r || v[t[i].m] > v[t[t[i].c[0]].m]));
REQUIRE((t[t[i].c[1]].l > t[t[i].c[1]].r || v[t[i].m] > v[t[t[i].c[1]].m]));
}
}
}
}
#include <vector>
#include <array>
#include <functional>
#include <utility>
#include <catch2/catch_test_macros.hpp>
#include <catch2/catch_get_random_seed.hpp>
#include <bits/stdc++.h>
#line 2 "src/cartesian_tree.hpp"
#line 5 "src/cartesian_tree.hpp"
#line 2 "src/reverse_comparator.hpp"
#line 5 "src/reverse_comparator.hpp"
template <typename F> struct reverse_comparator_t {
F f;
template <typename Arg1, typename Arg2> constexpr bool operator() (Arg1&& arg1, Arg2&& arg2) & {
return f(std::forward<Arg2>(arg2), std::forward<Arg1>(arg1));
}
template <typename Arg1, typename Arg2> constexpr bool operator() (Arg1&& arg1, Arg2&& arg2) const& {
return f(std::forward<Arg2>(arg2), std::forward<Arg1>(arg1));
}
template <typename Arg1, typename Arg2> constexpr bool operator() (Arg1&& arg1, Arg2&& arg2) && {
return std::move(f)(std::forward<Arg2>(arg2), std::forward<Arg1>(arg1));
}
template <typename Arg1, typename Arg2> constexpr bool operator() (Arg1&& arg1, Arg2&& arg2) const&& {
return std::move(f)(std::forward<Arg2>(arg2), std::forward<Arg1>(arg1));
}
};
template <typename F> constexpr reverse_comparator_t<std::decay_t<F>> reverse_comparator(F&& f) {
return { std::forward<F>(f) };
}
#line 7 "src/cartesian_tree.hpp"
class CartesianTree {
public:
struct Node {
int l, m, r; // inclusive ranges
std::array<int, 2> c;
int p;
};
std::vector<Node> nodes;
int root = -1;
CartesianTree() {}
Node& operator [] (int idx) { return nodes[idx]; }
const Node& operator [] (int idx) const { return nodes[idx]; }
int size() const { return int(nodes.size()); }
private:
CartesianTree(std::vector<Node>&& nodes_, int root_) : nodes(std::move(nodes_)), root(root_) {}
public:
// min-cartesian-tree, with earlier cells tiebroken earlier
template <typename T, typename Comp = std::less<T>>
static CartesianTree build_min_tree(const std::vector<T>& v, Comp comp = Comp()) {
std::vector<Node> nodes(v.size()*2+1);
std::vector<int> stk; stk.reserve(v.size());
int root = -1;
for (int i = 0; i <= int(v.size()); i++) {
int cur = 2*i;
nodes[cur].l = i;
nodes[cur].r = i-1;
nodes[cur].m = i-1;
nodes[cur].c = {-1, -1};
while (!stk.empty() && (i == int(v.size()) || comp(v[i], v[nodes[stk.back()].m]))) {
int nxt = stk.back(); stk.pop_back();
nodes[cur].p = nxt;
nodes[nxt].c[1] = cur;
nodes[nxt].r = nodes[cur].r;
cur = nxt;
}
if (i == int(v.size())) {
root = cur;
break;
}
nodes[2*i+1].l = nodes[cur].l;
nodes[2*i+1].m = i;
nodes[cur].p = 2*i+1;
nodes[2*i+1].c[0] = cur;
stk.push_back(2*i+1);
}
nodes[root].p = -1;
return {std::move(nodes), root};
}
// max-cartesian-tree, with earlier cells tiebroken earlier
template <typename T, typename Comp = std::less<T>>
static CartesianTree build_max_tree(const std::vector<T>& v, Comp comp = Comp()) {
return build_min_tree(v, reverse_comparator(comp));
}
};
#line 2 "src/cartesian_tree.test.cpp"
#line 6 "src/cartesian_tree.test.cpp"
TEST_CASE("Cartesian Tree", "[cartesian_tree]") {
std::mt19937 mt(Catch::getSeed());
for (int sz : {0, 1, 2, 3, 5, 8, 13}) {
std::vector<int> v(sz);
iota(v.begin(), v.end(), 0);
shuffle(v.begin(), v.end(), mt);
{
CartesianTree t = CartesianTree::build_min_tree(v);
for (int i = 1; i < int(t.size()); i += 2) {
REQUIRE(t[i].m == i/2);
REQUIRE(t[i].l <= t[i].m);
REQUIRE(t[i].m <= t[i].r);
REQUIRE(t[t[i].c[0]].l == t[i].l);
REQUIRE(t[t[i].c[0]].r == t[i].m-1);
REQUIRE(t[t[i].c[1]].l == t[i].m+1);
REQUIRE(t[t[i].c[1]].r == t[i].r);
REQUIRE((t[t[i].c[0]].l > t[t[i].c[0]].r || v[t[i].m] < v[t[t[i].c[0]].m]));
REQUIRE((t[t[i].c[1]].l > t[t[i].c[1]].r || v[t[i].m] < v[t[t[i].c[1]].m]));
}
}
{
CartesianTree t = CartesianTree::build_max_tree(v);
for (int i = 1; i < int(t.size()); i += 2) {
REQUIRE(t[i].m == i/2);
REQUIRE(t[i].l <= t[i].m);
REQUIRE(t[i].m <= t[i].r);
REQUIRE(t[t[i].c[0]].l == t[i].l);
REQUIRE(t[t[i].c[0]].r == t[i].m-1);
REQUIRE(t[t[i].c[1]].l == t[i].m+1);
REQUIRE(t[t[i].c[1]].r == t[i].r);
REQUIRE((t[t[i].c[0]].l > t[t[i].c[0]].r || v[t[i].m] > v[t[t[i].c[0]].m]));
REQUIRE((t[t[i].c[1]].l > t[t[i].c[1]].r || v[t[i].m] > v[t[t[i].c[1]].m]));
}
}
}
}
// clang-format off
// @formatter:off
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#pragma GCC diagnostic ignored "-Wmultistatement-macros"
#include <bits/stdc++.h>
#include <catch2/catch_test_macros.hpp>
#include <catch2/catch_get_random_seed.hpp>
// src/reverse_comparator.hpp
template<typename F>struct reverse_comparator_t{
F f;
template<typename Arg1,typename Arg2>constexpr bool operator()(Arg1&&arg1,Arg2&&arg2)&{
return f(std::forward<Arg2>(arg2),std::forward<Arg1>(arg1));
}
template<typename Arg1,typename Arg2>constexpr bool operator()(Arg1&&arg1,Arg2&&arg2)const&{
return f(std::forward<Arg2>(arg2),std::forward<Arg1>(arg1));
}
template<typename Arg1,typename Arg2>constexpr bool operator()(Arg1&&arg1,Arg2&&arg2)&&{
return std::move(f)(std::forward<Arg2>(arg2),std::forward<Arg1>(arg1));
}
template<typename Arg1,typename Arg2>constexpr bool operator()(Arg1&&arg1,Arg2&&arg2)const&&{
return std::move(f)(std::forward<Arg2>(arg2),std::forward<Arg1>(arg1));
}
};
template<typename F>constexpr reverse_comparator_t<std::decay_t<F>>reverse_comparator(F&&f){
return{std::forward<F>(f)};
}
// src/cartesian_tree.hpp
class CartesianTree{
public:
struct Node{
int l,m,r;
std::array<int,2>c;
int p;
};
std::vector<Node>nodes;
int root=-1;
CartesianTree(){}
Node&operator[](int idx){return nodes[idx];}
const Node&operator[](int idx)const{return nodes[idx];}
int size()const{return int(nodes.size());}
private:
CartesianTree(std::vector<Node>&&nodes_,int root_):nodes(std::move(nodes_)),root(root_){}
public:
template<typename T,typename Comp=std::less<T>>
static CartesianTree build_min_tree(const std::vector<T>&v,Comp comp=Comp()){
std::vector<Node>nodes(v.size()*2+1);
std::vector<int>stk;stk.reserve(v.size());
int root=-1;
for(int i=0;i<=int(v.size());i++){
int cur=2*i;
nodes[cur].l=i;
nodes[cur].r=i-1;
nodes[cur].m=i-1;
nodes[cur].c={-1,-1};
while(!stk.empty()&&(i==int(v.size())||comp(v[i],v[nodes[stk.back()].m]))){
int nxt=stk.back();stk.pop_back();
nodes[cur].p=nxt;
nodes[nxt].c[1]=cur;
nodes[nxt].r=nodes[cur].r;
cur=nxt;
}
if(i==int(v.size())){
root=cur;
break;
}
nodes[2*i+1].l=nodes[cur].l;
nodes[2*i+1].m=i;
nodes[cur].p=2*i+1;
nodes[2*i+1].c[0]=cur;
stk.push_back(2*i+1);
}
nodes[root].p=-1;
return{std::move(nodes),root};
}
template<typename T,typename Comp=std::less<T>>
static CartesianTree build_max_tree(const std::vector<T>&v,Comp comp=Comp()){
return build_min_tree(v,reverse_comparator(comp));
}
};
// src/cartesian_tree.test.cpp
TEST_CASE("Cartesian Tree","[cartesian_tree]"){
std::mt19937 mt(Catch::getSeed());
for(int sz:{0,1,2,3,5,8,13}){
std::vector<int>v(sz);
iota(v.begin(),v.end(),0);
shuffle(v.begin(),v.end(),mt);
{
CartesianTree t=CartesianTree::build_min_tree(v);
for(int i=1;i<int(t.size());i+=2){
REQUIRE(t[i].m==i/2);
REQUIRE(t[i].l<=t[i].m);
REQUIRE(t[i].m<=t[i].r);
REQUIRE(t[t[i].c[0]].l==t[i].l);
REQUIRE(t[t[i].c[0]].r==t[i].m-1);
REQUIRE(t[t[i].c[1]].l==t[i].m+1);
REQUIRE(t[t[i].c[1]].r==t[i].r);
REQUIRE((t[t[i].c[0]].l>t[t[i].c[0]].r||v[t[i].m]<v[t[t[i].c[0]].m]));
REQUIRE((t[t[i].c[1]].l>t[t[i].c[1]].r||v[t[i].m]<v[t[t[i].c[1]].m]));
}
}
{
CartesianTree t=CartesianTree::build_max_tree(v);
for(int i=1;i<int(t.size());i+=2){
REQUIRE(t[i].m==i/2);
REQUIRE(t[i].l<=t[i].m);
REQUIRE(t[i].m<=t[i].r);
REQUIRE(t[t[i].c[0]].l==t[i].l);
REQUIRE(t[t[i].c[0]].r==t[i].m-1);
REQUIRE(t[t[i].c[1]].l==t[i].m+1);
REQUIRE(t[t[i].c[1]].r==t[i].r);
REQUIRE((t[t[i].c[0]].l>t[t[i].c[0]].r||v[t[i].m]>v[t[t[i].c[0]].m]));
REQUIRE((t[t[i].c[1]].l>t[t[i].c[1]].r||v[t[i].m]>v[t[t[i].c[1]].m]));
}
}
}
}
#pragma GCC diagnostic pop
// clang-format on
// @formatter:on