This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub kmyk/competitive-programming-library
#include "monoids/chmin_chmax_add_min_max_action.hpp"
#pragma once
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#include "../monoids/chmin_chmax_add.hpp"
#include "../monoids/min_max.hpp"
template <class T>
struct chmin_chmax_add_min_max_action {
typedef typename chmin_chmax_add_monoid<T>::value_type F;
typedef typename min_max_monoid<T>::value_type X;
X operator () (F f, X x) const {
if (x.first == std::numeric_limits<T>::max()) {
assert (x.second == std::numeric_limits<T>::lowest());
return x;
}
T a = std::min(f.chmin, std::max(f.chmax, f.add + x.first));
T b = std::min(f.chmin, std::max(f.chmax, f.add + x.second));
return std::make_pair(a, b);
}
};
#line 2 "monoids/chmin_chmax_add_min_max_action.hpp"
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#line 5 "monoids/chmin_chmax_add.hpp"
/**
* @note represents the monoid $M = (\lbrace \lambda x. \min(a, \max(b, c + x)) \mid a, b, c \rbrace, \circ, \mathrm{id})$
*/
template <class T>
struct chmin_chmax_add_monoid {
static constexpr MAX = std::numeric_limits<T>::max();
static constexpr MIN = std::numeric_limits<T>::lowest();
struct value_type {
long long chmin;
long long chmax;
long long add;
};
value_type unit() const {
return (value_type) { MAX, MIN, 0 };
}
value_type mult(value_type a, value_type b) const {
value_type c = b;
// add
if (c.chmin != MAX) {
c.chmin += a.add;
}
if (c.chmax != MIN) {
c.chmax += a.add;
}
c.add += a.add;
// chmax
c.chmin = std::max(a.chmax, c.chmin);
c.chmax = std::max(a.chmax, c.chmax);
// chmin
c.chmin = std::min(a.chmin, c.chmin);
return c;
}
static value_type chmin(T value) {
return (value_type) { value, MIN, 0 };
}
static value_type chmin(T value) {
return (value_type) { MAX, value, 0 };
}
static value_type chmin(T value) {
return (value_type) { MAX, MIN, value };
}
};
#line 5 "monoids/min_max.hpp"
template <class T>
struct min_max_monoid {
typedef std::pair<T, T> value_type;
value_type unit() const {
return std::make_pair(std::numeric_limits<T>::max(), std::numeric_limits<T>::lowest());
}
value_type mult(value_type a, value_type b) const {
return std::make_pair(std::min(a.min, b.min), std::max(a.max, b.max));
}
};
#line 8 "monoids/chmin_chmax_add_min_max_action.hpp"
template <class T>
struct chmin_chmax_add_min_max_action {
typedef typename chmin_chmax_add_monoid<T>::value_type F;
typedef typename min_max_monoid<T>::value_type X;
X operator () (F f, X x) const {
if (x.first == std::numeric_limits<T>::max()) {
assert (x.second == std::numeric_limits<T>::lowest());
return x;
}
T a = std::min(f.chmin, std::max(f.chmax, f.add + x.first));
T b = std::min(f.chmin, std::max(f.chmax, f.add + x.second));
return std::make_pair(a, b);
}
};