iterable/longest_increasing_subsequence.hpp

• View this file on GitHub
• Last update: 2024-07-27 23:01:00+09:00
• Include: #include "iterable/longest_increasing_subsequence.hpp"

Depends on

• adaptor/internal/advanced_container.hpp
• adaptor/valarray.hpp
• adaptor/vector.hpp
• global/constants.hpp
• internal/concepts.hpp
• internal/dev_env.hpp
• internal/exception.hpp
• internal/type_traits.hpp
• internal/types.hpp
• iterable/internal/operation_base.hpp
• macro/basic.hpp
• macro/overload.hpp
• numeric/internal/mod.hpp
• numeric/limits.hpp
• snippet/aliases.hpp
• snippet/internal/types.hpp
• snippet/iterations.hpp
• structure/grid.hpp

Required by

• include/all.hpp
• include/iterable.hpp

Verified with

• verify/aizu-online-judge/itp1_1_a/0001.test.cpp
• verify/yosupo-judge/longest_increasing_subsequence/0000.test.cpp

Code

#pragma once


#include <algorithm>
#include <iterator>


#include "snippet/aliases.hpp"

#include "internal/dev_env.hpp"
#include "internal/types.hpp"

#include "structure/grid.hpp"

#include "adaptor/vector.hpp"


namespace uni {


template<bool STRICT, class T, class container = vector<T>>
struct lis : container {
    using size_type = typename internal::size_t;

    std::vector<size_type> indices, positions;

    lis() noexcept = default;

    template<std::ranges::input_range R>
    explicit lis(R&& range) noexcept(NO_EXCEPT) : lis(ALL(range)) {}

    template<std::input_iterator I, std::sentinel_for<I> S>
    lis(I first, S last) noexcept(NO_EXCEPT) : positions(std::ranges::distance(first, last), -1) {
        this->reserve(std::ranges::distance(first, last));

        size_type pos = 0;
        for(auto itr=first; itr!=last; ++pos, ++itr) {
            typename container::iterator bound;

            if constexpr(STRICT) bound = std::ranges::lower_bound(*this, *itr);
            else bound = std::ranges::upper_bound(*this, *itr);

            this->positions[pos] = static_cast<size_type>(std::ranges::distance(std::ranges::begin(*this), bound));

            if(std::ranges::end(*this) == bound) this->emplace_back(*itr);
            else *bound = *itr;
        }

        size_type target = std::ranges::max(this->positions);

        for(size_type i = static_cast<size_type>(this->positions.size()); --i >= 0;){
            if(this->positions[i] == target) {
                this->operator[](target) = *(first + i);
                this->indices.emplace_back(i);
                --target;
            }
        }

        std::ranges::reverse(this->indices);
    }
};


} // namespace uni

#line 2 "iterable/longest_increasing_subsequence.hpp"


#include <algorithm>
#include <iterator>


#line 2 "snippet/aliases.hpp"


#include <cstdint>
#include <utility>
#include <vector>
#include <ranges>


#line 2 "internal/dev_env.hpp"


#ifdef LOCAL_JUDGE
    inline constexpr bool DEV_ENV = true;
    inline constexpr bool NO_EXCEPT = false;
#else
    inline constexpr bool DEV_ENV = false;
    inline constexpr bool NO_EXCEPT = true;
#endif // LOCAL_JUDGE


#if __cplusplus >= 202100L
    #define CPP20 true
    #define CPP23 true
#elif __cplusplus >= 202002L
    #define CPP20 true
    #define CPP23 false
#else
    #define CPP20 false
    #define CPP23 false
#endif
#line 2 "snippet/internal/types.hpp"

#line 4 "snippet/internal/types.hpp"

namespace uni {


using i16 = std::int16_t;
using u16 = std::uint16_t;

using i32 = std::int32_t;
using u32 = std::uint32_t;

using i64 = std::int64_t;
using u64 = std::uint64_t;

#ifdef __GNUC__

using i128 = __int128_t;
using u128 = __uint128_t;

using f128 = __float128;

#endif

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;


} // namespace uni
#line 12 "snippet/aliases.hpp"


#define until(...) while(!(__VA_ARGS__))

#define CONTINUE(...) { __VA_ARGS__; continue; }
#define BREAK(...) { __VA_ARGS__; break; }

#define ALL(x) std::ranges::begin((x)),std::ranges::end((x))
#define RALL(x) std::ranges::rbegin((x)),std::ranges::rend((x))


#define $F first
#define $S second


namespace uni {


constexpr char LN = '\n';
constexpr char SPC = ' ';


constexpr std::pair<int,int> DIRS4[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
constexpr std::pair<int,int> DIRS4P[] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 }, { 0, 0 } };
constexpr std::pair<int,int> DIRS8[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } };
constexpr std::pair<int,int> DIRS8P[] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 }, { 0, 0 } };


template<class T> using spair = std::pair<T,T>;


}  // namespace uni


namespace std {

using bit_reference = std::vector<bool>::reference;

bit_reference operator |= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a | b; }
bit_reference operator &= (bit_reference a, const bool b) noexcept(NO_EXCEPT) { return a = a & b; }

}
#line 9 "iterable/longest_increasing_subsequence.hpp"

#line 2 "internal/types.hpp"

#line 4 "internal/types.hpp"

namespace uni {

namespace internal {


using size_t = std::int64_t;

using int128_t = __int128_t;
using uint128_t = __uint128_t;


} // namesapce internal

} // namespace uni
#line 12 "iterable/longest_increasing_subsequence.hpp"

#line 2 "structure/grid.hpp"


#include <cassert>
#include <iostream>
#line 7 "structure/grid.hpp"
#include <string>
#include <type_traits>
#line 10 "structure/grid.hpp"
#include <initializer_list>
#line 12 "structure/grid.hpp"


#line 2 "snippet/iterations.hpp"

#line 2 "macro/overload.hpp"

#define $OVERLOAD2(arg0, arg1, cmd, ...) cmd
#define $OVERLOAD3(arg0, arg1, arg2, cmd, ...) cmd
#define $OVERLOAD4(arg0, arg1, arg2, arg3, cmd, ...) cmd
#define $OVERLOAD5(arg0, arg1, arg2, arg3, arg4, cmd, ...) cmd
#define $OVERLOAD6(arg0, arg1, arg2, arg3, arg4, arg5, cmd, ...) cmd
#line 2 "macro/basic.hpp"

#define TO_STRING_AUX(x) #x
#define TO_STRING(x) TO_STRING_AUX(x)

#define CONCAT_AUX(x, y) x##y
#define CONCAT(x, y) CONCAT_AUX(x, y)

#define UNPAREN_AUX(...) __VA_ARGS__
#define UNPAREN(...) __VA_ARGS__
#line 6 "snippet/iterations.hpp"


#define LOOP(n) REPI(CONCAT(_$, __COUNTER__), n)

#define REPI(i,n) for(std::remove_cvref_t<decltype(n)> i=0, CONCAT(i, $)=(n); i<CONCAT(i, $); ++i)
#define REPF(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); ++i)
#define REPIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); i+=(s))

#define REPR(i,n) for(auto i=(n); --i>=0;)
#define REPB(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); --i>=CONCAT(i, $);)
#define REPRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l)-1)/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); (i-=(s)))

#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)

#define FORO(i,n) for(int i=0, CONCAT(i, $)=static_cast<int>(n); i<=CONCAT(i, $); ++i)
#define FORI(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); ++i)
#define FORIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); i+=(s))

#define FORRO(i,n) for(auto i=(n); i>=0; --i)
#define FORR(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); i>=CONCAT(i, $); --i)
#define FORRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l))/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); i-=(s))

#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)

#define ITR1(e0,v) for(const auto &e0 : (v))
#define ITRP1(e0,v) for(auto e0 : (v))
#define ITRR1(e0,v) for(auto &e0 : (v))

#define ITR2(e0,e1,v) for(const auto [e0, e1] : (v))
#define ITRP2(e0,e1,v) for(auto [e0, e1] : (v))
#define ITRR2(e0,e1,v) for(auto &[e0, e1] : (v))

#define ITR3(e0,e1,e2,v) for(const auto [e0, e1, e2] : (v))
#define ITRP3(e0,e1,e2,v) for(auto [e0, e1, e2] : (v))
#define ITRR3(e0,e1,e2,v) for(auto &[e0, e1, e2] : (v))

#define ITR4(e0,e1,e2,e3,v) for(const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0,e1,e2,e3,v) for(auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0,e1,e2,e3,v) for(auto &[e0, e1, e2, e3] : (v))

#define ITR5(e0,e1,e2,e3,e4,v) for(const auto [e0, e1, e2, e3, e4] : (v))
#define ITRP5(e0,e1,e2,e3,e4,v) for(auto [e0, e1, e2, e3, e4] : (v))
#define ITRR5(e0,e1,e2,e3,e4,v) for(auto &[e0, e1, e2, e3, e4] : (v))

#define ITR(...) $OVERLOAD6(__VA_ARGS__, ITR5, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) $OVERLOAD6(__VA_ARGS__, ITRP5, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) $OVERLOAD6(__VA_ARGS__, ITRR5, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
#line 16 "structure/grid.hpp"

#line 19 "structure/grid.hpp"

#line 2 "global/constants.hpp"


#line 5 "global/constants.hpp"
#include <concepts>
#line 7 "global/constants.hpp"
#include <cmath>


#line 11 "global/constants.hpp"

#line 2 "internal/type_traits.hpp"


#line 9 "internal/type_traits.hpp"


#line 12 "internal/type_traits.hpp"


namespace uni {

namespace internal {


template<class... Ts> struct tuple_or_pair { using type = std::tuple<Ts...>; };
template<class T, class U> struct tuple_or_pair<T,U> { using type = std::pair<T, U>; };
template <class... Ts> using tuple_or_pair_t = typename tuple_or_pair<Ts...>::type;

template<class T>
constexpr std::underlying_type_t<T> to_underlying(const T& v) noexcept(NO_EXCEPT) {
    return static_cast<std::underlying_type_t<T>>(v);
}


template<class T, class... Ts>
using are_same = std::conjunction<std::is_same<T, Ts>...>;

template<class T, class... Ts>
inline constexpr bool are_same_v = are_same<T, Ts...>::value;


template<class T, class... Ts>
using is_same_as_any_of = std::disjunction<std::is_same<T, Ts>...>;

template<class T, class... Ts>
inline constexpr bool is_same_as_any_of_v = is_same_as_any_of<T, Ts...>::value;

template<class T, class... Ts>
concept same_as_any_of = is_same_as_any_of_v<T, Ts...>;


template<class Base, class... Derived>
using is_base_of_all = std::conjunction<std::is_base_of<Base, Derived>...>;

template<class Base, class... Derived>
inline constexpr bool is_base_of_all_v = is_base_of_all<Base, Derived...>::value;


template<class Base, class... Derived>
using is_base_of_any = std::disjunction<std::is_base_of<Base, Derived>...>;

template<class Base, class... Derived>
inline constexpr bool is_base_of_any_v = is_base_of_any<Base, Derived...>::value;


template<class T> struct remove_cvref {
  using type = typename std::remove_cv_t<std::remove_reference_t<T>>;
};

template<class T> using remove_cvref_t = typename remove_cvref<T>::type;


template<class T> struct literal_operator { static constexpr const char* value = ""; };

template<> struct literal_operator<unsigned> { static constexpr const char* value = "U"; };
template<> struct literal_operator<long> { static constexpr const char* value = "L"; };
template<> struct literal_operator<unsigned long> { static constexpr const char* value = "UL"; };
template<> struct literal_operator<long long> { static constexpr const char* value = "LL"; };
template<> struct literal_operator<unsigned long long> { static constexpr const char* value = "ULL"; };


template<> struct literal_operator<float> { static constexpr const char* value = "F"; };
template<> struct literal_operator<double> { static constexpr const char* value = "D"; };
template<> struct literal_operator<long double> { static constexpr const char* value = "LD"; };

#ifdef __SIZEOF_INT128__

template<> struct literal_operator<__int128_t> { static constexpr const char* value = "LLL"; };
template<> struct literal_operator<__uint128_t> { static constexpr const char* value = "ULLL"; };

#endif

template<class T> inline constexpr auto literal_operator_v = literal_operator<T>::value;


template <std::size_t N, typename... Types>
struct nth_type {};

template <class Head, class... Tail>
struct nth_type<0, Head, Tail...> {
	using type = Head;
};

template <std::size_t N, class Head, class... Tail>
struct nth_type<N, Head, Tail...> : public nth_type<N - 1, Tail...> {};

template <std::size_t N, typename... Types>
using nth_type_t = typename nth_type<N, Types...>::type;


template<template <class...> class, class> struct is_template_of : std::false_type {};
template<template <class...> class Template, class... Args> struct is_template_of<Template, Template<Args...>> : std::true_type {};

template<template <class...> class Template, class Type>
inline constexpr bool is_template_of_v = is_template_of<Template, Type>::value;

template<class Type, template <class...> class Template>
concept substituted_from = is_template_of_v<Template, Type>;

template<template <class...> class Base, class Derived>
struct _is_basic_tempalte_of
{
    template<class... Ts>
    static constexpr std::true_type  test(const Base<Ts...> *);

    static constexpr std::false_type test(...);

    using type = decltype(test(std::declval<Derived*>()));
};


template<template <class...> class Base, class Derived>
using is_basic_tempalte_of = _is_basic_tempalte_of<Base, Derived>::type;

template<template <class...> class Base, class Derived>
inline constexpr bool is_basic_tempalte_of_v = is_basic_tempalte_of<Base, Derived>::value;

template<class Derived, template <class...> class Base>
concept derived_from_template = is_basic_tempalte_of_v<Base, Derived>;


template<class T> struct is_loggable {
    template<class U>
    static constexpr auto External(U &&v) -> decltype(_debug(v), std::true_type());
    static constexpr std::false_type External(...);

    template<class U>
    static constexpr auto Member(U &&v) -> decltype(v._debug(), std::true_type());
    static constexpr std::false_type Member(...);

    static constexpr bool value = (
      decltype(External(std::declval<T>()))::value ||
      decltype(Member(std::declval<T>()))::value
    );

};

template<class T>
inline constexpr auto is_loggable_v = is_loggable<T>::value;

template<class T>
concept loggable = is_loggable_v<T>;


template<class T> struct _has_iterator {
    template<class U>
    static constexpr auto ADL(U &&v) -> decltype(begin(v), end(v), std::true_type());
    static constexpr std::false_type ADL(...);

    template<class U>
    static constexpr auto STL(U &&v) -> decltype(std::begin(v), std::end(v), std::true_type());
    static constexpr std::false_type STL(...);

    template<class U>
    static constexpr auto Member(U &&v) -> decltype(v.begin(), v.end(), std::true_type());
    static constexpr std::false_type Member(...);
};

template<class T> struct has_iterator {
    struct ADL : decltype(_has_iterator<T>::ADL(std::declval<T>())) {};
    struct STL : decltype(_has_iterator<T>::STL(std::declval<T>())) {};
    struct Member : decltype(_has_iterator<T>::Member(std::declval<T>())) {};

    static constexpr auto adl_v = ADL::value;
    static constexpr auto stl_v = STL::value;
    static constexpr auto member_v = Member::value;
};


template<class T>
struct is_iterable {
    static constexpr bool value =  has_iterator<T>::adl_v || has_iterator<T>::stl_v || has_iterator<T>::member_v;
};

template<class T>
inline constexpr auto is_iterable_v = is_iterable<T>::value;

template<class T>
concept iterable = is_iterable_v<T>;

namespace iterator_resolver {


template<class T>
inline constexpr auto begin(T&& v) noexcept(NO_EXCEPT) {
    static_assert(is_iterable_v<T>);
    if constexpr(has_iterator<T>::member_v) {
        return v.begin();
    }
    else {  // ADL
        using std::begin;
        return begin(std::forward<T>(v));
    }
}

template<class T>
inline constexpr auto end(T&& v) noexcept(NO_EXCEPT) {
    static_assert(is_iterable_v<T>);
    if constexpr(has_iterator<T>::member_v) {
        return v.end();
    }
    else {  // ADL
        using std::end;
        return end(std::forward<T>(v));
    }
}


};


template<class C> using iterator_t = decltype(iterator_resolver::begin(std::declval<C&>()));

template<class C> using container_size_t = decltype(std::size(std::declval<C&>()));


template<bool Const, class T>
using maybe_const_t = std::conditional_t<Const, const T, T>;


template<class T> using with_ref = T&;
template<class T> concept can_reference = requires { typename with_ref<T>; };


} // namespace internal

}  // namespace uni
#line 2 "internal/exception.hpp"


namespace uni {

namespace internal {


template<class... T> inline constexpr bool EXCEPTION_ON_TYPE = false;
template<auto T> inline constexpr bool EXCEPTION_ON_VALUE = false;


} // namespace internal

} // namespace uni
#line 14 "global/constants.hpp"

#line 2 "numeric/limits.hpp"


#include <limits>
#line 6 "numeric/limits.hpp"


#line 9 "numeric/limits.hpp"

#line 11 "numeric/limits.hpp"


namespace uni {


template<class T>
struct numeric_limits : std::numeric_limits<T> {
    static constexpr long double FLOAT_EPSILON = 1E-14;

    static constexpr T arithmetic_infinity() noexcept(NO_EXCEPT) {
        return std::numeric_limits<T>::max() / 2 - 1;
    }

    static constexpr T arithmetic_negative_infinity() noexcept(NO_EXCEPT) {
        return std::numeric_limits<T>::lowest() / 2 + 1;
    }

    static constexpr T arithmetic_epsilon() noexcept(NO_EXCEPT) {
        if constexpr(std::is_floating_point_v<T>) {
            return numeric_limits::FLOAT_EPSILON;
        }
        else {
            return 0;
        }
    }
};


constexpr i32 INF32 = numeric_limits<i32>::arithmetic_infinity();
constexpr i64 INF64 = numeric_limits<i64>::arithmetic_infinity();

template<class T>
constexpr T INF = numeric_limits<T>::arithmetic_infinity();

template<class T>
constexpr T EPSILON = numeric_limits<T>::arithmetic_epsilon();


} // namespace uni
#line 16 "global/constants.hpp"


namespace uni {


namespace internal {
    template<class T>
    consteval auto get_pi() {
        if constexpr(std::integral<T>) {
            return static_cast<T>(3);
        }
        else if constexpr(std::same_as<T, float>) {
            return M_PIf;
        }
        else if constexpr(std::same_as<T, double>) {
            return M_PI;
        }
        else if constexpr(std::same_as<T, ld>) {
            return M_PIl;
        }
        else {
            static_assert(EXCEPTION_ON_TYPE<T>);
        }
    }
} // namespace internal


template<class T = ld>
constexpr auto PI = internal::get_pi<T>();


enum class comparison : std::uint8_t {
    equal_to,
    not_equal_to,

    equals = equal_to,
    eq = equal_to,

    under,
    over,
    or_under,
    or_over,

    less = under,
    more = over,

    less_than = under,
    more_than = over,
    not_less_than = or_over,
    not_more_than = or_under,

    leq = or_under,
    geq = or_over
};


enum class interval_notation : std::uint8_t {
    right_open,
    left_open,
    open,
    closed,
};


enum class replacement_policy : std::uint8_t {
    insert_sync,
    overwrite_sync,
    overwrite_async
};


enum class rotation : std::int8_t {
    clockwise,

    counter_clockwise,
    anti_clockwise = counter_clockwise,
};


enum class positional_relation : std::int8_t {
    clockwise,

    counter_clockwise,
    anti_clockwise = counter_clockwise,

    backward,
    forward,

    in,
    on,
    out,

    included = in,
    inscribed,
    intersecting,
    circumscribed,
    distant,
};


enum class alignment : std::int8_t {
    left,
    center,
    right
};


} // namespace uni
#line 21 "structure/grid.hpp"

#line 2 "adaptor/vector.hpp"


#line 6 "adaptor/vector.hpp"


#line 2 "adaptor/internal/advanced_container.hpp"


#line 8 "adaptor/internal/advanced_container.hpp"

#line 11 "adaptor/internal/advanced_container.hpp"

#line 2 "internal/concepts.hpp"


#line 8 "internal/concepts.hpp"
#include <functional>


namespace uni {

namespace internal {


template<class R, class T>
concept convertibel_range = std::convertible_to<std::ranges::range_value_t<R>, T>;


template<class T, class V>
concept item_or_convertible_range = std::convertible_to<T, V> || convertibel_range<T, V>;


template<class Structure>
concept available =
    requires () {
        typename Structure;
    };

template<
    template<class...> class Structure,
    class... TemplateParameters
>
concept available_with = available<Structure<TemplateParameters...>>;


template<class T> concept arithmetic = std::is_arithmetic_v<T>;
template<class T> concept pointer = std::is_pointer_v<T>;
template<class T> concept structural = std::is_class_v<T>;


template<class Large, class Small>
concept has_double_digits_of = (std::numeric_limits<Large>::digits == 2 * std::numeric_limits<Small>::digits);


template<class Large, class Small>
concept has_more_digits_than = (std::numeric_limits<Large>::digits > std::numeric_limits<Small>::digits);

template<class Large, class Small>
concept has_or_more_digits_than = (std::numeric_limits<Large>::digits >= std::numeric_limits<Small>::digits);


template<class T>
concept has_static_zero = requires { T::zero; };

template<class T>
concept has_static_one = requires { T::one; };


template<class L, class R = L>
concept weakly_bitand_calcurable = requires (L lhs, R rhs) { lhs & rhs; };

template<class L, class R = L>
concept weakly_bitor_calcurable = requires (L lhs, R rhs) { lhs | rhs; };

template<class L, class R = L>
concept weakly_bitxor_calcurable = requires (L lhs, R rhs) { lhs ^ rhs; };

template<class L, class R = L>
concept weakly_addable = requires (L lhs, R rhs) { lhs + rhs; };

template<class L, class R = L>
concept weakly_subtractable = requires (L lhs, R rhs) { lhs - rhs; };

template<class L, class R = L>
concept weakly_multipliable = requires (L lhs, R rhs) { lhs * rhs; };

template<class L, class R = L>
concept weakly_divisable = requires (L lhs, R rhs) { lhs / rhs; };

template<class L, class R = L>
concept weakly_remainder_calculable = requires (L lhs, R rhs) { lhs % rhs; };


template<class L, class R = L>
concept weakly_bitand_assignable = requires (L lhs, R rhs) { lhs += rhs; };

template<class L, class R = L>
concept weakly_bitor_assignable = requires (L lhs, R rhs) { lhs |= rhs; };

template<class L, class R = L>
concept weakly_bitxor_assignable = requires (L lhs, R rhs) { lhs ^= rhs; };

template<class L, class R = L>
concept weakly_addition_assignable = requires (L lhs, R rhs) { lhs += rhs; };

template<class L, class R = L>
concept weakly_subtraction_assignable = requires (L lhs, R rhs) { lhs -= rhs; };

template<class L, class R = L>
concept weakly_multipliation_assignalbe = requires (L lhs, R rhs) { lhs *= rhs; };

template<class L, class R = L>
concept weakly_division_assignable = requires (L lhs, R rhs) { lhs /= rhs; };

template<class L, class R = L>
concept weakly_remainder_assignable = requires (L lhs, R rhs) { lhs /= rhs; };


template<class L, class R = L>
concept bitand_calculable =
    weakly_bitand_calcurable<L, R> &&
    weakly_bitand_calcurable<std::invoke_result_t<std::bit_and<>&, L, R>, R> &&
    weakly_bitand_calcurable<L, std::invoke_result_t<std::bit_and<>&, L, R>> &&
    weakly_bitand_calcurable<std::invoke_result_t<std::bit_and<>&, L, R>, std::invoke_result_t<std::bit_and<>&, L, R>>;

template<class L, class R = L>
concept bitor_calculable =
    weakly_bitor_calcurable<L, R> &&
    weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, R> &&
    weakly_bitor_calcurable<L, std::invoke_result_t<std::bit_or<>&, L, R>> &&
    weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, std::invoke_result_t<std::bit_or<>&, L, R>>;

template<class L, class R = L>
concept bitxor_calculable =
    weakly_bitxor_calcurable<L, R> &&
    weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, R> &&
    weakly_bitxor_calcurable<L, std::invoke_result_t<std::bit_xor<>&, L, R>> &&
    weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, std::invoke_result_t<std::bit_xor<>&, L, R>>;

template<class L, class R = L>
concept addable =
    weakly_addable<L, R> &&
    weakly_addable<std::invoke_result_t<std::plus<>&, L, R>, R> &&
    weakly_addable<L, std::invoke_result_t<std::plus<>&, L, R>> &&
    weakly_addable<std::invoke_result_t<std::plus<>&, L, R>, std::invoke_result_t<std::plus<>&, L, R>>;

template<class L, class R = L>
concept subtractable =
    weakly_subtractable<L, R> &&
    weakly_subtractable<std::invoke_result_t<std::minus<>&, L, R>, R> &&
    weakly_subtractable<L, std::invoke_result_t<std::minus<>&, L, R>> &&
    weakly_subtractable<std::invoke_result_t<std::minus<>&, L, R>, std::invoke_result_t<std::minus<>&, L, R>>;

template<class L, class R = L>
concept multipliable =
    weakly_multipliable<L, R> &&
    weakly_multipliable<std::invoke_result_t<std::multiplies<>&, L, R>, R> &&
    weakly_multipliable<L, std::invoke_result_t<std::multiplies<>&, L, R>> &&
    weakly_multipliable<std::invoke_result_t<std::multiplies<>&, L, R>, std::invoke_result_t<std::multiplies<>&, L, R>>;

template<class L, class R = L>
concept divisable =
    weakly_divisable<L, R> &&
    weakly_divisable<std::invoke_result_t<std::divides<>&, L, R>, R> &&
    weakly_divisable<L, std::invoke_result_t<std::divides<>&, L, R>> &&
    weakly_divisable<std::invoke_result_t<std::divides<>&, L, R>, std::invoke_result_t<std::divides<>&, L, R>>;

template<class L, class R = L>
concept remainder_calculable =
    weakly_remainder_calculable<L, R> &&
    weakly_remainder_calculable<std::invoke_result_t<std::modulus<>&, L, R>, R> &&
    weakly_remainder_calculable<L, std::invoke_result_t<std::modulus<>&, L, R>> &&
    weakly_remainder_calculable<std::invoke_result_t<std::modulus<>&, L, R>, std::invoke_result_t<std::modulus<>&, L, R>>;


template<class L, class R = L>
concept bitand_assignable =
    weakly_bitand_assignable<L, R> &&
    weakly_bitand_assignable<std::invoke_result_t<std::bit_and<>&, L, R>, R> &&
    weakly_bitand_assignable<L, std::invoke_result_t<std::bit_and<>&, L, R>> &&
    weakly_bitand_assignable<std::invoke_result_t<std::bit_and<>&, L, R>, std::invoke_result_t<std::bit_and<>&, L, R>>;

template<class L, class R = L>
concept bitor_assignable =
    weakly_bitor_calcurable<L, R> &&
    weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, R> &&
    weakly_bitor_calcurable<L, std::invoke_result_t<std::bit_or<>&, L, R>> &&
    weakly_bitor_calcurable<std::invoke_result_t<std::bit_or<>&, L, R>, std::invoke_result_t<std::bit_or<>&, L, R>>;

template<class L, class R = L>
concept bitxor_assignable =
    weakly_bitxor_calcurable<L, R> &&
    weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, R> &&
    weakly_bitxor_calcurable<L, std::invoke_result_t<std::bit_xor<>&, L, R>> &&
    weakly_bitxor_calcurable<std::invoke_result_t<std::bit_xor<>&, L, R>, std::invoke_result_t<std::bit_xor<>&, L, R>>;

template<class L, class R = L>
concept addition_assignable =
    weakly_addition_assignable<L, R> &&
    weakly_addition_assignable<std::remove_cvref_t<std::invoke_result_t<std::plus<>&, L, R>>, R> &&
    weakly_addition_assignable<L, std::invoke_result_t<std::plus<>&, L, R>> &&
    weakly_addition_assignable<std::remove_cvref_t<std::invoke_result_t<std::plus<>&, L, R>>, std::invoke_result_t<std::plus<>&, L, R>>;

template<class L, class R = L>
concept subtraction_assignable =
    weakly_subtraction_assignable<L, R> &&
    weakly_subtraction_assignable<std::remove_cvref_t<std::invoke_result_t<std::minus<>&, L, R>>, R> &&
    weakly_subtraction_assignable<L, std::invoke_result_t<std::minus<>&, L, R>> &&
    weakly_subtraction_assignable<std::remove_cvref_t<std::invoke_result_t<std::minus<>&, L, R>>, std::invoke_result_t<std::minus<>&, L, R>>;

template<class L, class R = L>
concept multipliation_assignalbe =
    weakly_multipliation_assignalbe<L, R> &&
    weakly_multipliation_assignalbe<std::remove_cvref_t<std::invoke_result_t<std::multiplies<>&, L, R>>, R> &&
    weakly_multipliation_assignalbe<L, std::invoke_result_t<std::multiplies<>&, L, R>> &&
    weakly_multipliation_assignalbe<std::remove_cvref_t<std::invoke_result_t<std::multiplies<>&, L, R>>, std::invoke_result_t<std::multiplies<>&, L, R>>;

template<class L, class R = L>
concept division_assignable =
    weakly_division_assignable<L, R> &&
    weakly_division_assignable<std::remove_cvref_t<std::invoke_result_t<std::divides<>&, L, R>>, R> &&
    weakly_division_assignable<L, std::invoke_result_t<std::divides<>&, L, R>> &&
    weakly_division_assignable<std::remove_cvref_t<std::invoke_result_t<std::divides<>&, L, R>>, std::invoke_result_t<std::divides<>&, L, R>>;

template<class L, class R = L>
concept remainder_assignable =
    weakly_remainder_assignable<L, R> &&
    weakly_remainder_assignable<std::remove_cvref_t<std::invoke_result_t<std::modulus<>&, L, R>>, R> &&
    weakly_remainder_assignable<L, std::invoke_result_t<std::modulus<>&, L, R>> &&
    weakly_remainder_assignable<std::remove_cvref_t<std::invoke_result_t<std::modulus<>&, L, R>>, std::invoke_result_t<std::modulus<>&, L, R>>;


template<class T>
concept weakly_incrementable =
    std::movable<T> &&
    requires (T v) {
        { ++v } -> std::same_as<T&>;
        v++;
    };

template<class T>
concept weakly_decrementable =
    std::movable<T> &&
    requires (T v) {
        { --v } -> std::same_as<T&>;
        v--;
    };


template<class T>
concept incrementable =
    std::regular<T> &&
    weakly_incrementable<T> &&
    requires (T v) {
        { v++ } -> std::same_as<T>;
    };

template<class T>
concept decrementable =
    std::regular<T> &&
    weakly_decrementable<T> &&
    requires (T v) {
        { v-- } -> std::same_as<T>;
    };


template<class L, class R = L>
concept weakly_arithmetic_operable =
    weakly_addable<L, R> &&
    weakly_subtractable<L, R> &&
    weakly_multipliable<L, R> &&
    weakly_divisable<L, R>;

template<class L, class R = L>
concept weakly_arithmetic_operation_assignable =
    weakly_addition_assignable<L, R> &&
    weakly_subtraction_assignable<L, R> &&
    weakly_multipliation_assignalbe<L, R> &&
    weakly_division_assignable<L, R>;

template<class L, class R = L>
concept arithmetic_operable =
    weakly_arithmetic_operable<L, R> &&
    addable<L, R> &&
    subtractable<L, R> &&
    multipliable<L, R> &&
    divisable<L, R>;

template<class L, class R = L>
concept arithmetic_operation_assignable =
    weakly_arithmetic_operation_assignable<L, R> &&
    addition_assignable<L, R> &&
    subtraction_assignable<L, R> &&
    multipliation_assignalbe<L, R> &&
    division_assignable<L, R>;


template<class T>
concept unary_addable =
    requires (T v) {
        { +v } -> std::same_as<T>;
    };

template<class T>
concept unary_subtractable =
    requires (T v) {
        { -v } -> std::same_as<T>;
    };


template<class T>
concept numeric =
    std::regular<T> &&
    arithmetic_operable<T> &&
    arithmetic_operation_assignable<T> &&
    weakly_incrementable<T> &&
    unary_addable<T> &&
    unary_subtractable<T>;


} // namespace internal

} // namespace uni
#line 15 "adaptor/internal/advanced_container.hpp"

#line 2 "numeric/internal/mod.hpp"


#line 6 "numeric/internal/mod.hpp"


namespace uni {


template<class T, class R>
    requires
        internal::remainder_calculable<T, R> &&
        internal::subtractable<T, R> &&
        internal::unary_subtractable<T>
inline T mod(T x, const R& r) noexcept(NO_EXCEPT) {
    if(x >= 0) return x % r;
    x = -x % r;
    if(x != 0) x = r - x;
    return x;
}


} // namespace uni
#line 2 "iterable/internal/operation_base.hpp"


#line 6 "iterable/internal/operation_base.hpp"
#include <sstream>
#include <numeric>


#line 11 "iterable/internal/operation_base.hpp"


namespace uni {


template<std::input_iterator I, std::sentinel_for<I> S>
std::string join(I first, S last, const char* sep = "") noexcept(NO_EXCEPT) {
    if(first == last) return "";
    std::ostringstream res;
    while(true) {
        res << *first;
        std::ranges::advance(first, 1);
        if(first == last) break;
        res << sep;
    }
    return res.str();
}


template<std::ranges::input_range R>
std::string join(R&& range, const char* sep = "") noexcept(NO_EXCEPT) {
    return join(ALL(range), sep);
}


template<class I, class T = std::iter_value_t<I>>
    requires std::sentinel_for<I, I>
T sum(I first, I last, const T& base = T()) noexcept(NO_EXCEPT) {
    return std::accumulate(first, last, base);
}

template<std::ranges::input_range R, class T = std::ranges::range_value_t<R>>
auto sum(R&& range, T base = T()) noexcept(NO_EXCEPT) {
    auto&& r = range | std::views::common;
    return sum(ALL(r), base);
}


} // namesapce uni
#line 18 "adaptor/internal/advanced_container.hpp"


#define UNI_ADVANCED_CONTAINER_OPERATOR(op_assign, op, concepts) \
    auto& operator op_assign(const value_type& v) noexcept(NO_EXCEPT) \
        requires concepts<value_type> \
    { \
        if constexpr(concepts<Base, value_type>) { \
            this->Base::operator op_assign(v); \
        } \
        else { \
            REP(itr, ALL(*this)) *itr op_assign v; \
        } \
        return *this; \
    } \
    \
    auto& operator op_assign(const advanced_container& rhs) noexcept(NO_EXCEPT) \
        requires concepts<value_type> \
    { \
        if constexpr(concepts<Base>) { \
            this->Base::operator op_assign(*rhs._base()); \
        } \
        else { \
            auto itr = std::ranges::begin(*this), rhs_itr = std::ranges::begin(rhs); \
            auto end = std::ranges::end(*this); \
            for(; itr != end; ++itr, ++rhs_itr) { \
                *itr op_assign *rhs_itr; \
            } \
        } \
        return *this; \
    } \
    \
    template<class T = value_type> \
        requires \
            concepts<value_type> && \
            (std::convertible_to<T, value_type> || std::same_as<T, advanced_container>) \
    friend auto operator op(advanced_container lhs, const T& rhs) noexcept(NO_EXCEPT) { \
        return lhs op_assign rhs; \
    } \
    \
    template<class T = value_type> \
        requires \
            concepts<value_type> && std::convertible_to<T, value_type> \
    friend auto operator op(const T& lhs, advanced_container rhs) noexcept(NO_EXCEPT) { \
        return advanced_container(rhs.size(), lhs) op_assign rhs; \
    }


namespace uni {

namespace internal {


template<class Base>
struct advanced_container : Base {
  private:
    inline Base* _base() noexcept(NO_EXCEPT) {
        return static_cast<Base*>(this);
    }
    inline const Base* _base() const noexcept(NO_EXCEPT) {
        return static_cast<const Base*>(this);
    }

  public:
    using Base::Base;

    advanced_container(const Base& base) : Base(base) {}

    using size_type = decltype(std::ranges::size(std::declval<Base>()));
    using value_type = Base::value_type;

    inline auto ssize() const noexcept(NO_EXCEPT) { return std::ranges::ssize(*this->_base()); }


    inline const auto& operator[](internal::size_t p) const noexcept(NO_EXCEPT) {
        p = p < 0 ? p + this->size() : p;
        assert(0 <= p && p < this->ssize());
        return this->Base::operator[](p);
    }

    inline auto& operator[](internal::size_t p) noexcept(NO_EXCEPT) {
        p = p < 0 ? p + this->size() : p;
        assert(0 <= p && p < this->ssize());
        return this->Base::operator[](p);
    }


    inline auto& fill(const value_type& v) noexcept(NO_EXCEPT) {
        std::ranges::fill(*this, v);
        return *this;
    }

    inline auto& swap(const size_type i, const size_type j) noexcept(NO_EXCEPT) {
        std::swap(this->operator[](i), this->operator[](j));
        return *this;
    }

    inline auto& sort() noexcept(NO_EXCEPT) {
        std::ranges::sort(*this);
        return *this;
    }

    template<class F>
    inline auto& sort(F&& f) noexcept(NO_EXCEPT) {
        std::ranges::sort(*this, std::forward<F>(f));
        return *this;
    }

    inline auto& stable_sort() noexcept(NO_EXCEPT) {
        std::ranges::stable_sort(*this);
        return *this;
    }

    template<class F>
    inline auto& stable_sort(F&& f) noexcept(NO_EXCEPT) {
        std::ranges::stable_sort(*this, std::forward<F>(f));
        return *this;
    }

    inline auto& reverse() noexcept(NO_EXCEPT) {
        std::ranges::reverse(*this);
        return *this;
    }

    inline auto count(const value_type& v) const noexcept(NO_EXCEPT) {
        return std::ranges::count(*this, v);
    }

    template<class F>
    inline auto count_if(F&& f) const noexcept(NO_EXCEPT) {
        return std::ranges::count_if(*this, std::forward<F>(f));
    }

    inline auto& resize(const size_type k) noexcept(NO_EXCEPT) {
        this->Base::resize(k);
        return *this;
    }
    inline auto& resize(const size_type k, const value_type v) noexcept(NO_EXCEPT) {
        this->Base::resize(k, v);
        return *this;
    }

    template<class F>
    inline auto& shuffle(F&& f) noexcept(NO_EXCEPT) {
        std::ranges::shuffle(*this, std::forward<F>(f));
        return *this;
    }

    inline auto& unique() noexcept(NO_EXCEPT) {
        const auto rest = std::ranges::unique(*this);
        this->erase(ALL(rest));
        return *this;
    }

    template<class T>
    inline auto binary_search(const T& v) noexcept(NO_EXCEPT) {
        return std::ranges::binary_search(*this, v);
    }

    template<class T>
    inline auto lower_bound(const T& v) noexcept(NO_EXCEPT) {
        return std::ranges::lower_bound(*this, v);
    }

    template<class T>
    inline auto upper_bound(const T& v) noexcept(NO_EXCEPT) {
        return std::ranges::upper_bound(*this, v);
    }

    inline auto join(const char* sep = "") noexcept(NO_EXCEPT) {
        return uni::join(*this, sep);
    }


    inline auto sum() const noexcept(NO_EXCEPT) { return uni::sum(*this); }


    inline auto max() const noexcept(NO_EXCEPT) { return std::ranges::max(*this->_base()); }
    inline auto min() const noexcept(NO_EXCEPT) { return std::ranges::min(*this); }


    inline auto begin() noexcept(NO_EXCEPT) { return std::ranges::begin(*this->_base()); }
    inline auto begin() const noexcept(NO_EXCEPT) { return std::ranges::begin(*this->_base()); }

    inline auto end() noexcept(NO_EXCEPT) { return std::ranges::end(*this->_base()); }
    inline auto end() const noexcept(NO_EXCEPT) { return std::ranges::end(*this->_base()); }


    UNI_ADVANCED_CONTAINER_OPERATOR(+=, +, internal::weakly_addition_assignable)
    UNI_ADVANCED_CONTAINER_OPERATOR(-=, -, internal::weakly_subtraction_assignable)
    UNI_ADVANCED_CONTAINER_OPERATOR(*=, *, internal::weakly_multipliation_assignalbe)
    UNI_ADVANCED_CONTAINER_OPERATOR(/=, /, internal::weakly_division_assignable)
    UNI_ADVANCED_CONTAINER_OPERATOR(%=, %, internal::weakly_remainder_assignable)
    UNI_ADVANCED_CONTAINER_OPERATOR(&=, &, internal::weakly_bitand_assignable)
    UNI_ADVANCED_CONTAINER_OPERATOR(|=, |, internal::weakly_bitor_assignable)
    UNI_ADVANCED_CONTAINER_OPERATOR(^=, ^, internal::weakly_bitxor_assignable)
};


} // namespace internal

} // namespace uni

#undef UNI_ADVANCED_CONTAINER_OPERATOR
#line 9 "adaptor/vector.hpp"


namespace uni {


template<class... Args>
using vector = internal::advanced_container<std::vector<Args...>>;


} // namespace uni
#line 2 "adaptor/valarray.hpp"


#line 6 "adaptor/valarray.hpp"
#include <valarray>
#line 11 "adaptor/valarray.hpp"

#line 14 "adaptor/valarray.hpp"

#line 16 "adaptor/valarray.hpp"


namespace uni {


template<class T> struct valarray : internal::advanced_container<std::valarray<T>> {
  private:
    using base = internal::advanced_container<std::valarray<T>>;

  public:
    using size_type = internal::size_t;

    using iterator = T*;
    using const_iterator = const T*;

  protected:
    inline bool _validate_index_in_right_open([[maybe_unused]] const size_type p) const noexcept(NO_EXCEPT) {
        return 0 <= p and p < this->size();
    }
    inline bool _validate_index_in_closed([[maybe_unused]] const size_type p) const noexcept(NO_EXCEPT) {
        return 0 <= p and p <= this->size();
    }
    inline bool _validate_rigth_open_interval([[maybe_unused]] const size_type l, [[maybe_unused]] const size_type r) const noexcept(NO_EXCEPT) {
        return 0 <= l and l <= r and r <= this->size();
    }

    inline size_type _positivize_index(const size_type p) const noexcept(NO_EXCEPT) {
        return p < 0 ? this->size() + p : p;
    }

  public:
    valarray() noexcept(NO_EXCEPT) {}

    explicit valarray(const std::size_t length, const T& val = T{}) noexcept(NO_EXCEPT) : base(val, length) {}

    template<std::input_iterator I, std::sentinel_for<I> S>
    valarray(I first, S last) noexcept(NO_EXCEPT) : base(std::ranges::distance(first, last)) { std::ranges::copy(first, last, std::ranges::begin(*this)); }

    template<class U> valarray(const U* pointer, const size_t n) noexcept(NO_EXCEPT) : base(pointer, n) {};

    valarray(const std::slice_array<T>& arr) noexcept(NO_EXCEPT) : base(arr) {};
    valarray(const std::gslice_array<T>& arr) noexcept(NO_EXCEPT) : base(arr) {};
    valarray(const std::mask_array<T>& arr) noexcept(NO_EXCEPT) : base(arr) {};
    valarray(const std::indirect_array<T>& arr) noexcept(NO_EXCEPT) : base(arr) {};
    valarray(const std::initializer_list<T>& init) noexcept(NO_EXCEPT) : base(init) {}
    valarray(const internal::advanced_container<std::valarray<T>>& arr) noexcept(NO_EXCEPT) : base(arr) {}

  #ifdef __GNUC__
    template<class Dom> valarray(const std::_Expr<Dom,T>& expr) noexcept(NO_EXCEPT) : base(expr) {}
  #endif

    inline auto size() const noexcept(NO_EXCEPT) { return static_cast<size_type>(this->base::size()); }

    inline void reserve(const size_type) noexcept(NO_EXCEPT) { /* do nothing */ }

    template<std::input_iterator I, std::sentinel_for<I> S>
    inline void assign(I first, S last) noexcept(NO_EXCEPT) {
        this->resize(std::ranges::distance(first, last));
        std::ranges::copy(first, last, std::ranges::begin(*this));
    }

    inline void assign(const std::size_t length, const T& val = T{}) noexcept(NO_EXCEPT) {
        this->base::resize(length, val);
    }

    inline void resize(const std::size_t length, const T& val = T{}) noexcept(NO_EXCEPT) {
        base temp = *this;
        this->assign(length, val);
        std::move(std::begin(temp), std::min(std::end(temp), std::next(std::begin(temp), length)), std::begin(*this));
    }

    inline const T& operator[](size_type pos) const noexcept(NO_EXCEPT) {
        pos = this->_positivize_index(pos), assert(this->_validate_index_in_right_open(pos));
        return this->base::operator[](pos);
    }
    inline T& operator[](size_type pos) noexcept(NO_EXCEPT) {
        pos = this->_positivize_index(pos), assert(this->_validate_index_in_right_open(pos));
        return this->base::operator[](pos);
    }

    inline const T& back() const noexcept(NO_EXCEPT) { return *std::prev(this->end()); }
    inline T& back() noexcept(NO_EXCEPT) { return *std::prev(this->end()); }

    inline const T& front() const noexcept(NO_EXCEPT) { return *this->begin(); }
    inline T& front() noexcept(NO_EXCEPT) { return *this->begin(); }

    inline auto rbegin() noexcept(NO_EXCEPT) { return std::make_reverse_iterator(std::ranges::end(*this)); }
    inline auto rend() noexcept(NO_EXCEPT) { return std::make_reverse_iterator(std::ranges::begin(*this)); }

    inline auto rbegin() const noexcept(NO_EXCEPT) { return std::make_reverse_iterator(std::ranges::end(*this)); }
    inline auto rend() const noexcept(NO_EXCEPT) { return std::make_reverse_iterator(std::ranges::begin(*this)); }
};


} // namespace uni
#line 24 "structure/grid.hpp"


namespace uni {

namespace internal {

namespace grid_impl {


template<class T>
struct container_base {
    using value_type = T;
    using size_type = internal::size_t;

  private:
    size_type _h, _w;

  protected:
    inline void _validate_index(__attribute__ ((unused)) const size_type i, __attribute__ ((unused)) const size_type j) const noexcept(NO_EXCEPT) {
        assert(0 <= i and i < this->height());
        assert(0 <= j and j < this->width());
    }

    inline size_type _positivize_row_index(const size_type x) const noexcept(NO_EXCEPT) {
        return x < 0 ? this->height() + x : x;
    }
    inline size_type _positivize_col_index(const size_type x) const noexcept(NO_EXCEPT) {
        return x < 0 ? this->width() + x : x;
    }

  public:
    container_base() = default;
    container_base(const size_type h, const size_type w) noexcept(NO_EXCEPT) : _h(h), _w(w) {}

    void resize(const size_type h, const size_type w) noexcept(NO_EXCEPT) {
        this->_h = h, this->_w = w;
    }

    inline size_type height() const noexcept(NO_EXCEPT) { return this->_h; }
    inline size_type width() const noexcept(NO_EXCEPT) { return this->_w; }

    inline size_type id(const size_type i, const size_type j) const noexcept(NO_EXCEPT) {
        const size_type _i = this->_positivize_row_index(i);
        const size_type _j = this->_positivize_col_index(j);
        this->_validate_index(_i, _j);
        return _i * this->width() + _j;
    }

    inline size_type id(const std::pair<size_type,size_type>& p) const noexcept(NO_EXCEPT) {
        return this->id(p.first, p.second);
    }

    inline std::pair<size_type,size_type> pos(const size_type id) const noexcept(NO_EXCEPT) {
        return { id / this->width(), id % this->width() };
    }
};

template<class Base>
struct regular_container : Base, container_base<typename Base::value_type::value_type> {
    using row_type = typename Base::value_type;
    using value_type = typename row_type::value_type;

    using size_type = internal::size_t;

    explicit regular_container(const size_type n = 0) noexcept(NO_EXCEPT) : regular_container(n, n) {}

    regular_container(const size_type h, const size_type w, const value_type &val = value_type()) noexcept(NO_EXCEPT)
      : Base(h, row_type(w, val)), container_base<value_type>(h, w)
    {}

    regular_container(const std::initializer_list<row_type> init_list) noexcept(NO_EXCEPT) : Base(init_list) {
        const auto rows = std::ranges::ssize(init_list);
        const size_type first_cols = init_list.begin()->size();

        if constexpr (DEV_ENV) { ITR(init_row, init_list) assert((size_type)init_row.size() == first_cols); }

        this->container_base<value_type>::resize(rows, first_cols);
    }

    inline void assign(const regular_container &source) noexcept(NO_EXCEPT) {
        this->resize(source.height(), source.width());
        this->Base::assign(ALL(source));
    }

    inline void assign(const size_type h, const size_type w, const value_type &val = value_type()) noexcept(NO_EXCEPT) {
        this->container_base<value_type>::resize(h, w);
        this->Base::resize(h);
        ITRR(row, *this) row.assign(w, val);
    }

    inline void resize(const size_type h, const size_type w) noexcept(NO_EXCEPT) {
        this->container_base<value_type>::resize(h, w);
        this->Base::resize(h);
        ITRR(row, *this) row.resize(w);
    }

    inline auto& operator()(const size_type i, const size_type j) noexcept(NO_EXCEPT) {
        const size_type _i = this->_positivize_row_index(i);
        const size_type _j = this->_positivize_col_index(j);
        this->_validate_index(_i, _j);
        return (*this)[_i][_j];
    }

    inline const auto& operator()(const size_type i, const size_type j) const noexcept(NO_EXCEPT) {
        const size_type _i = this->_positivize_row_index(i);
        const size_type _j = this->_positivize_col_index(j);
        this->_validate_index(_i, _j);
        return (*this)[_i][_j];
    }

    inline auto& operator()(const std::pair<size_type,size_type>& p) noexcept(NO_EXCEPT) {
        return this->operator()(p.first, p.second);
    }

    inline const auto& operator()(const std::pair<size_type,size_type>& p) const noexcept(NO_EXCEPT) {
        return this->operator()(p.first, p.second);
    }
};

template<class Base>
struct unfolded_container : Base, container_base<typename Base::value_type> {
    using value_type = typename Base::value_type;
    using size_type = internal::size_t;

    explicit unfolded_container(size_type n = 0) noexcept(NO_EXCEPT) : unfolded_container(n, n) {}

    unfolded_container(const size_type h, const size_type w, const value_type &val = value_type()) noexcept(NO_EXCEPT)
      : Base(h * w, val), container_base<value_type>(h, w)
    {}

    unfolded_container(std::initializer_list<std::initializer_list<value_type>> init_list) noexcept(NO_EXCEPT) {
        const auto rows = std::ranges::ssize(init_list);
        const auto first_cols = std::ranges::ssize(std::ranges::begin(init_list));

        this->resize(rows, first_cols);

        {
            size_type index = 0;
            for(
                    auto itr = std::ranges::begin(init_list), itr_end = std::ranges::end(init_list);
                    itr!=itr_end;
                    ++itr
            )
            {
                assert((size_type)itr->size() == first_cols);
                for(auto v=itr->begin(), v_end=itr->end(); v!=v_end; ++v) (*this)[index++] = *v;
            }
        }
    }

    inline void assign(const unfolded_container &source) noexcept(NO_EXCEPT) {
        this->resize(source.height(), source.width());
        this->Base::assign(ALL(source));
    }

    inline void assign(const size_type h, const size_type w, const value_type &val = value_type()) noexcept(NO_EXCEPT) {
        this->container_base<value_type>::resize(h, w);
        this->Base::assign(h * w, val);
    }

    inline void resize(const size_type h, const size_type w) noexcept(NO_EXCEPT) {
        this->container_base<value_type>::resize(h, w);
        this->Base::resize(h * w);
    }

    inline value_type& operator()(const size_type i, const size_type j) noexcept(NO_EXCEPT) {
        const size_type _i = this->_positivize_row_index(i);
        const size_type _j = this->_positivize_col_index(j);
        return this->operator[](this->id(_i, _j));
    }

    inline value_type& operator()(const std::pair<size_type,size_type>& p) noexcept(NO_EXCEPT) {
        return this->operator()(this->id(p.first, p.second));
    }

    inline const value_type& operator()(const std::pair<size_type,size_type>& p) const noexcept(NO_EXCEPT) {
        return this->operator()(this->id(p.first, p.second));
    }
};


}  // namespace grid_impl


template<class Container>
struct grid_core : Container {
    using Container::Container;

    using value_type = Container::value_type;
    using size_type = internal::size_t;

    enum class invert_direction { vertical, horizontal };
    enum class rotate_direction { counter_clockwise, clockwise };


    inline bool is_valid(const size_type i, const size_type j) const noexcept(NO_EXCEPT) {
        return 0 <= i and i < this->height() and 0 <= j and j < this->width();
    }

    inline bool is_valid(const std::pair<size_type, size_type>& p) const noexcept(NO_EXCEPT) {
        return this->is_valid(p.first, p.second);
    }


    template<std::input_iterator I, std::sentinel_for<I> S>
    inline auto vicinities(const size_type i, const size_type j, I dirs_first, S dirs_last) const noexcept(NO_EXCEPT) {
        std::vector<std::pair<size_type, size_type>> res;
        REP(itr, dirs_first, dirs_last) {
            const size_type ii = i + itr->first, jj = j + itr->second;
            if(this->is_valid(ii, jj)) res.emplace_back(ii, jj);
        }
        return res;
    }

    template<class I, class C>
    inline auto vicinities(const std::pair<size_type, size_type>& p, const C dirs) const noexcept(NO_EXCEPT) {
        return this->vicinities(p.first, p.second, ALL(dirs));
    }

    inline auto vicinities4(const size_type i, const size_type j) const noexcept(NO_EXCEPT) { return this->vicinities(i, j, ALL(DIRS4)); }
    inline auto vicinities4(const std::pair<size_type, size_type>& p) const noexcept(NO_EXCEPT) { return this->vicinities(p.first, p.second, ALL(DIRS4)); }

    inline auto vicinities8(const size_type i, const size_type j) const noexcept(NO_EXCEPT) { return this->vicinities(i, j, ALL(DIRS8)); }
    inline auto vicinities8(const std::pair<size_type, size_type>& p) const noexcept(NO_EXCEPT) { return this->vicinities(p.first, p.second, ALL(DIRS8)); }


    template<invert_direction DIRECTION = invert_direction::vertical>
    inline grid_core& invert() noexcept(NO_EXCEPT) {
        grid_core res(this->height(), this->width());
        REP(i, this->height()) REP(j, this->width()) {
            if constexpr (DIRECTION == invert_direction::vertical) {
                res(i,j) = (*this)(this->height()-i-1,j);
            }
            else {
                res(i,j) = (*this)(i, this->width()-j-1);
            }
        }
        this->assign(res);
        return *this;
    }

    template<rotate_direction DIRECTION = rotate_direction::clockwise>
    inline grid_core& rotate(const size_type k) noexcept(NO_EXCEPT) {
        grid_core res = *this;
        REP(i, k) { res = res.rotate<DIRECTION>(); }
        this->assign(res);
        return *this;
    }

    template<rotate_direction DIRECTION = rotate_direction::clockwise>
    inline grid_core& rotate() noexcept(NO_EXCEPT) {
        grid_core res(this->width(), this->height());
        REP(i, this->width()) REP(j, this->height()) {
            if constexpr (DIRECTION == rotate_direction::clockwise) {
                res(i,j) = (*this)(this->height()-j-1,i);
            }
            else {
                res(i,j) = (*this)(j,this->width()-i-1);
            }
        }
        this->assign(res);
        return *this;
    }

    inline grid_core& transpose() noexcept(NO_EXCEPT) {
        grid_core res(this->width(), this->height());
        REP(i, this->width()) REP(j, this->height()) {
            res(i,j) = (*this)(j,i);
        }
        this->assign(res);
        return *this;
    }
};


} // namespace internal


template<class T, class row_type = vector<T>, class Base = vector<row_type>>
using grid = internal::grid_core<internal::grid_impl::regular_container<Base>>;

template<class T, class row_type = valarray<T>, class Base = vector<row_type>>
using valgrid = internal::grid_core<internal::grid_impl::regular_container<Base>>;

template<class T, class Base = vector<T>>
using unfolded_grid = internal::grid_core<internal::grid_impl::unfolded_container<Base>>;

template<class T, class Base = valarray<T>>
using unfolded_valgrid = internal::grid_core<internal::grid_impl::unfolded_container<Base>>;


} // namespace uni
#line 14 "iterable/longest_increasing_subsequence.hpp"

#line 16 "iterable/longest_increasing_subsequence.hpp"


namespace uni {


template<bool STRICT, class T, class container = vector<T>>
struct lis : container {
    using size_type = typename internal::size_t;

    std::vector<size_type> indices, positions;

    lis() noexcept = default;

    template<std::ranges::input_range R>
    explicit lis(R&& range) noexcept(NO_EXCEPT) : lis(ALL(range)) {}

    template<std::input_iterator I, std::sentinel_for<I> S>
    lis(I first, S last) noexcept(NO_EXCEPT) : positions(std::ranges::distance(first, last), -1) {
        this->reserve(std::ranges::distance(first, last));

        size_type pos = 0;
        for(auto itr=first; itr!=last; ++pos, ++itr) {
            typename container::iterator bound;

            if constexpr(STRICT) bound = std::ranges::lower_bound(*this, *itr);
            else bound = std::ranges::upper_bound(*this, *itr);

            this->positions[pos] = static_cast<size_type>(std::ranges::distance(std::ranges::begin(*this), bound));

            if(std::ranges::end(*this) == bound) this->emplace_back(*itr);
            else *bound = *itr;
        }

        size_type target = std::ranges::max(this->positions);

        for(size_type i = static_cast<size_type>(this->positions.size()); --i >= 0;){
            if(this->positions[i] == target) {
                this->operator[](target) = *(first + i);
                this->indices.emplace_back(i);
                --target;
            }
        }

        std::ranges::reverse(this->indices);
    }
};


} // namespace uni

Back to top page