numeric/stern_brocot_tree.hpp

• View this file on GitHub
• Last update: 2024-07-27 23:01:00+09:00
• Include: #include "numeric/stern_brocot_tree.hpp"
• Link: https://maspypy.github.io/library/nt/stern_brocot_tree.hpp

Depends on

• adaptor/internal/advanced_container.hpp
• adaptor/vector.hpp
• internal/concepts.hpp
• internal/dev_env.hpp
• internal/types.hpp
• iterable/internal/operation_base.hpp
• macro/basic.hpp
• macro/overload.hpp
• numeric/internal/mod.hpp
• snippet/aliases.hpp
• snippet/internal/types.hpp
• snippet/iterations.hpp

Required by

• include/all.hpp
• include/numeric.hpp

Verified with

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

Code

#pragma once


#include <ranges>
#include <utility>

#include "snippet/aliases.hpp"

#include "internal/concepts.hpp"

#include "adaptor/vector.hpp"


namespace uni {


// Thanks to: https://maspypy.github.io/library/nt/stern_brocot_tree.hpp
template<
    class Value = i32,
    class Middle = i64,
    class Large = i128,
    class Fraction = spair<Value>, std::ranges::range Path = uni::vector<Value>
>
struct stern_brocot_tree {
    using value_type = Value;
    using middle_type = Middle;
    using large_type = middle_type;
    using path_type = Path;
    using fraction_type = Fraction;

    static constexpr std::tuple<path_type, fraction_type, fraction_type> path_and_rang(const fraction_type x) {
        path_type path;
        fraction_type l = { 0, 1 }, r = { 1, 0 };
        fraction_type m = { 1, 1 };
        middle_type det_l = l.first * x.second - l.second * x.first;
        middle_type det_r = r.first * x.second - r.second * x.first;
        middle_type det_m = det_l + det_r;
        while(true) {
            if(det_m == 0) break;
            middle_type k = uni::div_ceil(-det_m, det_r);
            path.emplace_back(k);
            l = { l.first + k * r.first, l.second + k * r.second };
            m = { l.first + r.first, l.second + r.second };
            det_l += k * det_r;
            det_m += k * det_r;
            if(det_m == 0) break;
            k = uni::div_ceil(det_m, -det_l);
            path.emplace_back(k);
            r = { r.first + k * l.first, r.second + k * l.second };
            m = { l.first + r.first, l.second + r.second };
            det_r += k * det_l;
            det_m += k * det_l;
        }
        return { path, l, r };
    }

    static constexpr path_type path(const fraction_type x) {
        const auto [ path, l, r ] = path_and_rang(x);
        return path;
    }

    static constexpr spair<fraction_type> range(const fraction_type x) {
        const auto [ path, l, r ] = path_and_rang(x);
        return { l, r };
    }

    // x in range(y)
    static constexpr bool in_subtree(const fraction_type x, const fraction_type y) {
        const auto [ l, r ] = range(y);
        const bool ok_l = static_cast<middle_type>(x.first) * l.second - static_cast<middle_type>(x.second) * l.first > 0;
        const bool ok_r = static_cast<middle_type>(r.first) * x.second - static_cast<middle_type>(r.second) * x.first > 0;
        return ok_l && ok_r;
    }

    template<class T = middle_type, class Frac = spair<middle_type>>
    static constexpr Frac from_path(const path_type &p) {
        Frac l = { 0, 1 }, r = { 1, 0 };
        FOR(i, std::ranges::size(p)) {
            middle_type k = p[i];
            if((i & 1) == 0) {
                l.first += static_cast<T>(k) * r.first;
                l.second += static_cast<T>(k) * r.second;
            }
            if((i & 1) == 1) {
                r.first += static_cast<T>(k) * l.first;
                r.second += static_cast<T>(k) * l.second;
            }
        }
        return { l.first + r.first, l.second + r.second };
    }

    static constexpr spair<fraction_type> children(const fraction_type x) {
        const auto [ l, r ] = range(x);
        const fraction_type lc = { l.first + x.first, l.second + x.second };
        const fraction_type rc = { x.first + r.first, x.second + r.second };
        return { lc, rc };
    }

    static constexpr fraction_type lowest_common_ancestor(const fraction_type x, const fraction_type y) {
        const auto px = path(x);
        const auto py = path(y);
        path_type path;
        FOR(i, uni::min(std::ranges::ssize(px), std::ranges::ssize(py))) {
            middle_type k = uni::min(px[i], py[i]);
            path.emplace_back(k);
            if(k < px[i] || k < py[i]) break;
        }
        return from_path(path);
    }

    static constexpr fraction_type ancestor(const fraction_type x, middle_type dep) {
        fraction_type l = { 0, 1 }, r = { 1, 0 };
        fraction_type m = { 1, 1 };
        middle_type det_l = l.first * x.second - l.second * x.first;
        middle_type det_r = r.first * x.second - r.second * x.first;
        middle_type det_m = det_l + det_r;
        while(true) {
            if(det_m == 0 || dep == 0) break;
            middle_type k = uni::min(dep, uni::div_ceil(-det_m, det_r));
            l = { l.first + k * r.first, l.second + k * r.second };
            m = { l.first + r.first, l.second + r.second };
            det_l += k * det_r;
            det_m += k * det_r;
            dep -= k;
            if(det_m == 0 || dep == 0) break;
            k = uni::min(dep, uni::div_ceil(det_m, -det_l));
            r = {r.first + k * l.first, r.second + k * l.second };
            m = { l.first + r.first, l.second + r.second };
            det_r += k * det_l;
            det_m += k * det_l;
            dep -= k;
        }
        if(dep == 0) return m;
        return { -1, -1 };
    }

    static constexpr std::string to_string(const path_type &p) {
        std::string res;
        char c = 'L';
        ITR(x, p) {
            c = 'L' + 'R' - c;
            if(x == 0) continue;
            res += c;
            res += " " + std::to_string(x);
        }
        return res;
    }
};


} // namespace uni

#line 2 "numeric/stern_brocot_tree.hpp"


#include <ranges>
#include <utility>

#line 2 "snippet/aliases.hpp"


#include <cstdint>
#line 6 "snippet/aliases.hpp"
#include <vector>
#line 8 "snippet/aliases.hpp"


#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 8 "numeric/stern_brocot_tree.hpp"

#line 2 "internal/concepts.hpp"


#include <type_traits>
#include <concepts>
#line 7 "internal/concepts.hpp"
#include <limits>
#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 10 "numeric/stern_brocot_tree.hpp"

#line 2 "adaptor/vector.hpp"


#line 5 "adaptor/vector.hpp"
#include <algorithm>


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


#include <cassert>
#line 8 "adaptor/internal/advanced_container.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 11 "adaptor/internal/advanced_container.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 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 5 "iterable/internal/operation_base.hpp"
#include <iterator>
#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 12 "numeric/stern_brocot_tree.hpp"


namespace uni {


// Thanks to: https://maspypy.github.io/library/nt/stern_brocot_tree.hpp
template<
    class Value = i32,
    class Middle = i64,
    class Large = i128,
    class Fraction = spair<Value>, std::ranges::range Path = uni::vector<Value>
>
struct stern_brocot_tree {
    using value_type = Value;
    using middle_type = Middle;
    using large_type = middle_type;
    using path_type = Path;
    using fraction_type = Fraction;

    static constexpr std::tuple<path_type, fraction_type, fraction_type> path_and_rang(const fraction_type x) {
        path_type path;
        fraction_type l = { 0, 1 }, r = { 1, 0 };
        fraction_type m = { 1, 1 };
        middle_type det_l = l.first * x.second - l.second * x.first;
        middle_type det_r = r.first * x.second - r.second * x.first;
        middle_type det_m = det_l + det_r;
        while(true) {
            if(det_m == 0) break;
            middle_type k = uni::div_ceil(-det_m, det_r);
            path.emplace_back(k);
            l = { l.first + k * r.first, l.second + k * r.second };
            m = { l.first + r.first, l.second + r.second };
            det_l += k * det_r;
            det_m += k * det_r;
            if(det_m == 0) break;
            k = uni::div_ceil(det_m, -det_l);
            path.emplace_back(k);
            r = { r.first + k * l.first, r.second + k * l.second };
            m = { l.first + r.first, l.second + r.second };
            det_r += k * det_l;
            det_m += k * det_l;
        }
        return { path, l, r };
    }

    static constexpr path_type path(const fraction_type x) {
        const auto [ path, l, r ] = path_and_rang(x);
        return path;
    }

    static constexpr spair<fraction_type> range(const fraction_type x) {
        const auto [ path, l, r ] = path_and_rang(x);
        return { l, r };
    }

    // x in range(y)
    static constexpr bool in_subtree(const fraction_type x, const fraction_type y) {
        const auto [ l, r ] = range(y);
        const bool ok_l = static_cast<middle_type>(x.first) * l.second - static_cast<middle_type>(x.second) * l.first > 0;
        const bool ok_r = static_cast<middle_type>(r.first) * x.second - static_cast<middle_type>(r.second) * x.first > 0;
        return ok_l && ok_r;
    }

    template<class T = middle_type, class Frac = spair<middle_type>>
    static constexpr Frac from_path(const path_type &p) {
        Frac l = { 0, 1 }, r = { 1, 0 };
        FOR(i, std::ranges::size(p)) {
            middle_type k = p[i];
            if((i & 1) == 0) {
                l.first += static_cast<T>(k) * r.first;
                l.second += static_cast<T>(k) * r.second;
            }
            if((i & 1) == 1) {
                r.first += static_cast<T>(k) * l.first;
                r.second += static_cast<T>(k) * l.second;
            }
        }
        return { l.first + r.first, l.second + r.second };
    }

    static constexpr spair<fraction_type> children(const fraction_type x) {
        const auto [ l, r ] = range(x);
        const fraction_type lc = { l.first + x.first, l.second + x.second };
        const fraction_type rc = { x.first + r.first, x.second + r.second };
        return { lc, rc };
    }

    static constexpr fraction_type lowest_common_ancestor(const fraction_type x, const fraction_type y) {
        const auto px = path(x);
        const auto py = path(y);
        path_type path;
        FOR(i, uni::min(std::ranges::ssize(px), std::ranges::ssize(py))) {
            middle_type k = uni::min(px[i], py[i]);
            path.emplace_back(k);
            if(k < px[i] || k < py[i]) break;
        }
        return from_path(path);
    }

    static constexpr fraction_type ancestor(const fraction_type x, middle_type dep) {
        fraction_type l = { 0, 1 }, r = { 1, 0 };
        fraction_type m = { 1, 1 };
        middle_type det_l = l.first * x.second - l.second * x.first;
        middle_type det_r = r.first * x.second - r.second * x.first;
        middle_type det_m = det_l + det_r;
        while(true) {
            if(det_m == 0 || dep == 0) break;
            middle_type k = uni::min(dep, uni::div_ceil(-det_m, det_r));
            l = { l.first + k * r.first, l.second + k * r.second };
            m = { l.first + r.first, l.second + r.second };
            det_l += k * det_r;
            det_m += k * det_r;
            dep -= k;
            if(det_m == 0 || dep == 0) break;
            k = uni::min(dep, uni::div_ceil(det_m, -det_l));
            r = {r.first + k * l.first, r.second + k * l.second };
            m = { l.first + r.first, l.second + r.second };
            det_r += k * det_l;
            det_m += k * det_l;
            dep -= k;
        }
        if(dep == 0) return m;
        return { -1, -1 };
    }

    static constexpr std::string to_string(const path_type &p) {
        std::string res;
        char c = 'L';
        ITR(x, p) {
            c = 'L' + 'R' - c;
            if(x == 0) continue;
            res += c;
            res += " " + std::to_string(x);
        }
        return res;
    }
};


} // namespace uni

Back to top page