test/src/datastructure/convex_hull_trick/line_add_get_min.test.cpp

View this file on GitHub
Last update: 2023-09-15 20:02:25+09:00
Problem: https://judge.yosupo.jp/problem/line_add_get_min

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"

#include <iostream>
#include <tuple>
#include <vector>

#include "library/datastructure/convex_hull_trick.hpp"
using suisen::ConvexHullTrick;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;

    ConvexHullTrick<long long> cht;
    for (int i = 0; i < n; ++i) {
        long long a, b;
        std::cin >> a >> b;
        cht.add_line(a, b);
    }
    for (int i = 0; i < q; ++i) {
        int t;
        std::cin >> t;
        if (t == 0) {
            long long a, b;
            std::cin >> a >> b;
            cht.add_line(a, b);
        } else {
            int x;
            std::cin >> x;
            std::cout << (long long) cht.query(x) << '\n';
        }
    }
    return 0;
}

#line 1 "test/src/datastructure/convex_hull_trick/line_add_get_min.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"

#include <iostream>
#include <tuple>
#include <vector>

#line 1 "library/datastructure/convex_hull_trick.hpp"



#include <cassert>
#include <limits>
#include <set>

#line 1 "library/type_traits/type_traits.hpp"



#line 6 "library/type_traits/type_traits.hpp"
#include <type_traits>

namespace suisen {
    template <typename ...Constraints> using constraints_t = std::enable_if_t<std::conjunction_v<Constraints...>, std::nullptr_t>;

    template <typename T, typename = std::nullptr_t> struct bitnum { static constexpr int value = 0; };
    template <typename T> struct bitnum<T, constraints_t<std::is_integral<T>>> { static constexpr int value = std::numeric_limits<std::make_unsigned_t<T>>::digits; };
    template <typename T> static constexpr int bitnum_v = bitnum<T>::value;
    template <typename T, size_t n> struct is_nbit { static constexpr bool value = bitnum_v<T> == n; };
    template <typename T, size_t n> static constexpr bool is_nbit_v = is_nbit<T, n>::value;

    template <typename T, typename = std::nullptr_t> struct safely_multipliable { using type = T; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 32>>> { using type = long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_signed<T>, is_nbit<T, 64>>> { using type = __int128_t; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 32>>> { using type = unsigned long long; };
    template <typename T> struct safely_multipliable<T, constraints_t<std::is_unsigned<T>, is_nbit<T, 64>>> { using type = __uint128_t; };
    template <typename T> using safely_multipliable_t = typename safely_multipliable<T>::type;

    template <typename T, typename = void> struct rec_value_type { using type = T; };
    template <typename T> struct rec_value_type<T, std::void_t<typename T::value_type>> {
        using type = typename rec_value_type<typename T::value_type>::type;
    };
    template <typename T> using rec_value_type_t = typename rec_value_type<T>::type;

    template <typename T> class is_iterable {
        template <typename T_> static auto test(T_ e) -> decltype(e.begin(), e.end(), std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_iterable_v = is_iterable<T>::value;
    template <typename T> class is_writable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::ostream&>() << e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_writable_v = is_writable<T>::value;
    template <typename T> class is_readable {
        template <typename T_> static auto test(T_ e) -> decltype(std::declval<std::istream&>() >> e, std::true_type{});
        static std::false_type test(...);
    public:
        static constexpr bool value = decltype(test(std::declval<T>()))::value;
    };
    template <typename T> static constexpr bool is_readable_v = is_readable<T>::value;
} // namespace suisen

#line 9 "library/datastructure/convex_hull_trick.hpp"

namespace suisen {
    namespace internal::convex_hull_trick {
        template <typename T>
        struct Line {
            // f(x)=ax+b,m=max{x|f=argmin_{f' in S}{f'(x)}}
            mutable T a, b, m;
            Line(const T& a, const T& b, const T& m) : a(a), b(b), m(m) {}
            bool operator<(const Line<T>& rhs) const { return a < rhs.a; }
            bool operator<(const T& x) const { return not (m < x); }
        };

        template <typename T, std::enable_if_t<std::is_integral<T>::value, std::nullptr_t> = nullptr>
        inline T div(const T& num, const T& den) {
            return num / den - ((num ^ den) < 0 and num % den);
        }
        template <typename T, std::enable_if_t<std::negation<std::is_integral<T>>::value, std::nullptr_t> = nullptr>
        inline T div(const T& num, const T& den) {
            return num / den;
        }
    }

    template <typename T, bool is_min_query = true>
    class ConvexHullTrick : std::multiset<internal::convex_hull_trick::Line<T>, std::less<>> {
        using iterator = typename std::multiset<internal::convex_hull_trick::Line<T>>::iterator;
        using MultT = safely_multipliable_t<T>;
        using Line = internal::convex_hull_trick::Line<T>;

        static constexpr T inf = std::numeric_limits<T>::max();
    public:
        bool has_line() const {
            return not this->empty();
        }

        void add_line(T slope, T intercept) {
            if constexpr (not is_min_query) slope = -slope, intercept = -intercept;
            auto it = this->emplace(slope, intercept, inf);
            auto itl = it;
            for (; itl != this->begin();) {
                if (update_intersec_right(--itl, it)) {
                    ++itl;
                    break;
                }
            }
            auto itm = this->erase(itl, it), itr = std::next(itm);
            if (not update_intersec_right(itm, itr)) {
                update_intersec_right(--itm, itr);
            }
            for (it = itm; itr != this->end();) {
                itm = itr++;
                if (itr != this->end() and itm->m <= itr->m) {
                    update_intersec_right(it, itr);
                } else {
                    break;
                }
            }
            if (it != itm) this->erase(std::next(it), itm);
        }

        MultT query(T x) {
            assert(not this->empty());
            const iterator l = --(this-> template lower_bound<T>(x));
            auto res = (MultT) l->a * x + l->b;
            if constexpr (is_min_query) {
                return res;
            } else {
                return -res;
            }
        }
    private:
        // updates r->m and returns whether l is necessary or not.
        bool update_intersec_right(iterator l, iterator r) {
            if (r == this->end()) return true;
            if (l->a == r->a) {
                r->m = r->b <= l->b ? inf : -inf;
            } else {
                r->m = internal::convex_hull_trick::div(r->b - l->b, l->a - r->a);
            }
            return l->m > r->m;
        }
    };
    template <typename T>
    using MinCHT = ConvexHullTrick<T, /* is_min_query = */ true>;
    template <typename T>
    using MaxCHT = ConvexHullTrick<T, /* is_min_query = */ false>;
} // namespace suisen


#line 8 "test/src/datastructure/convex_hull_trick/line_add_get_min.test.cpp"
using suisen::ConvexHullTrick;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    std::cin >> n >> q;

    ConvexHullTrick<long long> cht;
    for (int i = 0; i < n; ++i) {
        long long a, b;
        std::cin >> a >> b;
        cht.add_line(a, b);
    }
    for (int i = 0; i < q; ++i) {
        int t;
        std::cin >> t;
        if (t == 0) {
            long long a, b;
            std::cin >> a >> b;
            cht.add_line(a, b);
        } else {
            int x;
            std::cin >> x;
            std::cout << (long long) cht.query(x) << '\n';
        }
    }
    return 0;
}