cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub suisen-cp/cp-library-cpp

:heavy_check_mark: 2D セグメント木 (点群が疎な場合)
(library/datastructure/segment_tree/segment_tree_2d_sparse.hpp)

2D セグメント木 (点群が疎な場合)

Depends on

Verified with

Code

#ifndef SUISEN_SEGMENT_TREE_2D_SPARSE
#define SUISEN_SEGMENT_TREE_2D_SPARSE

#include <algorithm>
#include <tuple>

#include "library/datastructure/segment_tree/segment_tree.hpp"

namespace suisen {

template <typename T, T(*op)(T, T), T(*e)()>
class SegmentTree2DSparse {
    public:
        SegmentTree2DSparse() = default;
        explicit SegmentTree2DSparse(int x_num) : n(x_num + 1), m(ceil_pow2(n)), data(m * 2), points(), pos_x(), pos_y(m * 2) {}

        void add_point(int x, int y) {
            built = false;
            pos_x.push_back(x);
            points.emplace_back(x, y);
        }

        void build() {
            static constexpr int inf = std::numeric_limits<int>::max();
            built = true;
            pos_x.push_back(inf);
            std::sort(pos_x.begin(), pos_x.end());
            pos_x.erase(std::unique(pos_x.begin(), pos_x.end()), pos_x.end());
            assert(int(pos_x.size()) <= n);
            for (const auto &[x, y] : points) {
                for (int k = comp_x(x) + m; k; k >>= 1) pos_y[k].push_back(y);
            }
            for (int k = 1; k < 2 * m; ++k) {
                pos_y[k].push_back(inf);
                std::sort(pos_y[k].begin(), pos_y[k].end());
                pos_y[k].erase(std::unique(pos_y[k].begin(), pos_y[k].end()), pos_y[k].end());
                data[k] = SegmentTree<T, op, e>(pos_y[k].size());
            }
        }

        T prod(int l, int r, int d, int u) const {
            return (*this)(l, r, d, u);
        }
        T operator()(int l, int r, int d, int u) const {
            assert(built);
            T res_l = e(), res_r = e();
            for (l = comp_x(l) + m, r = comp_x(r) + m; l < r; l >>= 1, r >>= 1) {
                if (l & 1) res_l = op(res_l, prod(l++, d, u));
                if (r & 1) res_r = op(prod(--r, d, u), res_r);
            }
            return op(res_l, res_r);
        }
        T all_prod() const {
            assert(built);
            return data[1].all_prod();
        }

        const T& get(int x, int y) const {
            assert(built);
            int i = comp_x(x), j = comp_y(i + m, y);
            assert(pos_x[i] == x and pos_y[i + m][j] == y);
            return data[i + m].get(j);
        }
        void set(int x, int y, const T &val) {
            (*this)[{x, y}] = val;
        }
        auto operator[](const std::pair<int, int> &p) {
            int x, y;
            std::tie(x, y) = p;
            return UpdateProxyObject { const_cast<T&>(get(x, y)), [this, k = comp_x(x) + m, y]{ update_from(k, y); } };
        }

        template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, T>> = nullptr>
        int max_up(int l, int r, int d, const Pred &f) const {
            assert(built);
            int res = std::numeric_limits<int>::max();
            for (l = comp_x(l) + m, r = comp_x(r) + m; l < r; l >>= 1, r >>= 1) {
                if (l & 1) res = std::min(res, max_up(l++, d, f));
                if (r & 1) res = std::min(res, max_up(--r, d, f));
            }
            return res;
        }
        template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, T>> = nullptr>
        int min_down(int l, int r, int u, const Pred &f) const {
            assert(built);
            int res = std::numeric_limits<int>::min();
            for (l = comp_x(l) + m, r = comp_x(r) + m; l < r; l >>= 1, r >>= 1) {
                if (l & 1) res = std::max(res, min_down(l++, u, f));
                if (r & 1) res = std::max(res, min_down(--r, u, f));
            }
            return res;
        }

    private:
        int n, m;
        std::vector<SegmentTree<T, op, e>> data;
        std::vector<std::pair<int, int>> points;
        std::vector<int> pos_x;
        std::vector<std::vector<int>> pos_y;
        bool built = true;

        static constexpr int ceil_pow2(int n) {
            int m = 1;
            while (m < n) m <<= 1;
            return m;
        }

        int comp_x(int x) const {
            return std::lower_bound(pos_x.begin(), pos_x.end(), x) - pos_x.begin();
        }
        int comp_y(int k, int y) const {
            return std::lower_bound(pos_y[k].begin(), pos_y[k].end(), y) - pos_y[k].begin();
        }

        T prod(int k, int d, int u) const {
            return data[k](comp_y(k, d), comp_y(k, u));
        }

        template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, T>> = nullptr>
        int max_up(int k, int d, const Pred &f) const {
            const int u = data[k].max_right(comp_y(k, d), f);
            return u == int(pos_y[k].size()) ? std::numeric_limits<int>::max() : pos_y[k][u];
        }
        template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, T>> = nullptr>
        int min_down(int k, int u, const Pred &f) const {
            const int d = data[k].min_left(comp_y(k, u), f);
            return d == 0 ? std::numeric_limits<int>::min() : pos_y[k][d - 1] + 1;
        }

        void update(int k, int y) {
            int p = comp_y(k, y);
            assert(pos_y[k][p] == y);
            if (k < m) {
                int l = comp_y(k * 2, y), r = comp_y(k * 2 + 1, y);
                T lv = pos_y[k * 2 + 0][l] == y ? data[k * 2 + 0].get(l) : e();
                T rv = pos_y[k * 2 + 1][r] == y ? data[k * 2 + 1].get(r) : e();
                data[k][p] = op(lv, rv);
            } else {
                data[k][p] = T(data[k][p]);
            }
        }
        void update_from(int k, int y) {
            for (; k; k >>= 1) update(k, y);
        }
};

} // namespace suisen


#endif // SUISEN_SEGMENT_TREE_2D_SPARSE
#line 1 "library/datastructure/segment_tree/segment_tree_2d_sparse.hpp"



#include <algorithm>
#include <tuple>

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



#include <cassert>
#include <vector>

#line 1 "library/util/update_proxy_object.hpp"



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



#include <limits>
#include <iostream>
#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 5 "library/util/update_proxy_object.hpp"

namespace suisen {

template <typename T, typename UpdateFunc, constraints_t<std::is_invocable<UpdateFunc>> = nullptr>
struct UpdateProxyObject {
    public:
        UpdateProxyObject(T &v, UpdateFunc update) : v(v), update(update) {}
        operator T() const { return v; }
        auto& operator++() && { ++v, update(); return *this; }
        auto& operator--() && { --v, update(); return *this; }
        auto& operator+=(const T &val) && { v += val, update(); return *this; }
        auto& operator-=(const T &val) && { v -= val, update(); return *this; }
        auto& operator*=(const T &val) && { v *= val, update(); return *this; }
        auto& operator/=(const T &val) && { v /= val, update(); return *this; }
        auto& operator%=(const T &val) && { v %= val, update(); return *this; }
        auto& operator =(const T &val) && { v  = val, update(); return *this; }
        auto& operator<<=(const T &val) && { v <<= val, update(); return *this; }
        auto& operator>>=(const T &val) && { v >>= val, update(); return *this; }
        template <typename F, constraints_t<std::is_invocable_r<T, F, T>> = nullptr>
        auto& apply(F f) && { v = f(v), update(); return *this; }
    private:
        T &v;
        UpdateFunc update;
};

} // namespace suisen


#line 8 "library/datastructure/segment_tree/segment_tree.hpp"

namespace suisen {
template <typename T, T(*op)(T, T), T(*e)()>
class SegmentTree {
    public:
        SegmentTree() : SegmentTree(0) {}
        explicit SegmentTree(int n) : SegmentTree(std::vector<T>(n, e())) {}
        SegmentTree(const std::vector<T> &a) : n(a.size()), m(ceil_pow2(n)), data(2 * m, e()) {
            build(a);
        }

        void build(const std::vector<T> &a) {
            assert(int(a.size()) <= m);
            std::copy(a.begin(), a.end(), data.begin() + m);
            for (int k = m - 1; k > 0; --k) update(k);
        }
        const T& get(int i) const {
            assert(0 <= i and i < n);
            return data[i + m];
        }
        T operator()(int l, int r) const {
            T res_l = e(), res_r = e();
            for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
                if (l & 1) res_l = op(res_l, data[l++]);
                if (r & 1) res_r = op(data[--r], res_r);
            }
            return op(res_l, res_r);
        }
        T prod(int l, int r) const { return (*this)(l, r); }
        T prefix_prod(int r) const { return (*this)(0, r); }
        T suffix_prod(int l) const { return (*this)(l, m); }
        T all_prod() const { return data[1]; }

        void set(int i, const T &val) {
            (*this)[i] = val;
        }
        auto operator[](int i) {
            assert(0 <= i and i < n);
            int k = i + m;
            return UpdateProxyObject { data[k], [this, k]{ update_from(k); } };
        }

        template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, T>> = nullptr>
        int max_right(int l, const Pred &f) const {
            assert(0 <= l and l <= n);
            assert(f(e));
            if (l == n) return n;
            l += m;
            T sum_l = e;
            do {
                while (l % 2 == 0) l >>= 1;
                if (not f(op(sum_l, data[l]))) {
                    while (l < m) {
                        l = 2 * l;
                        if (f(op(sum_l, data[l]))) sum_l = op(sum_l, data[l++]);
                    }
                    return l - m;
                }
                sum_l = op(sum_l, data[l]);
                l++;
            } while ((l & -l) != l);
            return n;
        }
        template <bool(*f)(T)>
        int max_right(int l) { return max_right(l, f); }

        template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, T>> = nullptr>
        int min_left(int r, const Pred &f) const {
            assert(0 <= r && r <= n);
            assert(f(e));
            if (r == 0) return 0;
            r += m;
            T sum_r = e;
            do {
                r--;
                while (r > 1 && (r % 2)) r >>= 1;
                if (not f(op(data[r], sum_r))) {
                    while (r < m) {
                        r = 2 * r + 1;
                        if (f(op(data[r], sum_r))) sum_r = op(data[r--], sum_r);
                    }
                    return r + 1 - m;
                }
                sum_r = op(data[r], sum_r);
            } while ((r & -r) != r);
            return 0;
        }
        template <bool(*f)(T)>
        int min_left(int l) { return min_left(l, f); }

    private:
        int n, m;
        std::vector<T> data;

        static constexpr int ceil_pow2(int n) {
            int m = 1;
            while (m < n) m <<= 1;
            return m;
        }
        void update_from(int k) {
            for (k >>= 1; k; k >>= 1) update(k);
        }
        void update(int k) {
            data[k] = op(data[k * 2], data[k * 2 + 1]);
        }
};
} // namespace suisen



#line 8 "library/datastructure/segment_tree/segment_tree_2d_sparse.hpp"

namespace suisen {

template <typename T, T(*op)(T, T), T(*e)()>
class SegmentTree2DSparse {
    public:
        SegmentTree2DSparse() = default;
        explicit SegmentTree2DSparse(int x_num) : n(x_num + 1), m(ceil_pow2(n)), data(m * 2), points(), pos_x(), pos_y(m * 2) {}

        void add_point(int x, int y) {
            built = false;
            pos_x.push_back(x);
            points.emplace_back(x, y);
        }

        void build() {
            static constexpr int inf = std::numeric_limits<int>::max();
            built = true;
            pos_x.push_back(inf);
            std::sort(pos_x.begin(), pos_x.end());
            pos_x.erase(std::unique(pos_x.begin(), pos_x.end()), pos_x.end());
            assert(int(pos_x.size()) <= n);
            for (const auto &[x, y] : points) {
                for (int k = comp_x(x) + m; k; k >>= 1) pos_y[k].push_back(y);
            }
            for (int k = 1; k < 2 * m; ++k) {
                pos_y[k].push_back(inf);
                std::sort(pos_y[k].begin(), pos_y[k].end());
                pos_y[k].erase(std::unique(pos_y[k].begin(), pos_y[k].end()), pos_y[k].end());
                data[k] = SegmentTree<T, op, e>(pos_y[k].size());
            }
        }

        T prod(int l, int r, int d, int u) const {
            return (*this)(l, r, d, u);
        }
        T operator()(int l, int r, int d, int u) const {
            assert(built);
            T res_l = e(), res_r = e();
            for (l = comp_x(l) + m, r = comp_x(r) + m; l < r; l >>= 1, r >>= 1) {
                if (l & 1) res_l = op(res_l, prod(l++, d, u));
                if (r & 1) res_r = op(prod(--r, d, u), res_r);
            }
            return op(res_l, res_r);
        }
        T all_prod() const {
            assert(built);
            return data[1].all_prod();
        }

        const T& get(int x, int y) const {
            assert(built);
            int i = comp_x(x), j = comp_y(i + m, y);
            assert(pos_x[i] == x and pos_y[i + m][j] == y);
            return data[i + m].get(j);
        }
        void set(int x, int y, const T &val) {
            (*this)[{x, y}] = val;
        }
        auto operator[](const std::pair<int, int> &p) {
            int x, y;
            std::tie(x, y) = p;
            return UpdateProxyObject { const_cast<T&>(get(x, y)), [this, k = comp_x(x) + m, y]{ update_from(k, y); } };
        }

        template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, T>> = nullptr>
        int max_up(int l, int r, int d, const Pred &f) const {
            assert(built);
            int res = std::numeric_limits<int>::max();
            for (l = comp_x(l) + m, r = comp_x(r) + m; l < r; l >>= 1, r >>= 1) {
                if (l & 1) res = std::min(res, max_up(l++, d, f));
                if (r & 1) res = std::min(res, max_up(--r, d, f));
            }
            return res;
        }
        template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, T>> = nullptr>
        int min_down(int l, int r, int u, const Pred &f) const {
            assert(built);
            int res = std::numeric_limits<int>::min();
            for (l = comp_x(l) + m, r = comp_x(r) + m; l < r; l >>= 1, r >>= 1) {
                if (l & 1) res = std::max(res, min_down(l++, u, f));
                if (r & 1) res = std::max(res, min_down(--r, u, f));
            }
            return res;
        }

    private:
        int n, m;
        std::vector<SegmentTree<T, op, e>> data;
        std::vector<std::pair<int, int>> points;
        std::vector<int> pos_x;
        std::vector<std::vector<int>> pos_y;
        bool built = true;

        static constexpr int ceil_pow2(int n) {
            int m = 1;
            while (m < n) m <<= 1;
            return m;
        }

        int comp_x(int x) const {
            return std::lower_bound(pos_x.begin(), pos_x.end(), x) - pos_x.begin();
        }
        int comp_y(int k, int y) const {
            return std::lower_bound(pos_y[k].begin(), pos_y[k].end(), y) - pos_y[k].begin();
        }

        T prod(int k, int d, int u) const {
            return data[k](comp_y(k, d), comp_y(k, u));
        }

        template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, T>> = nullptr>
        int max_up(int k, int d, const Pred &f) const {
            const int u = data[k].max_right(comp_y(k, d), f);
            return u == int(pos_y[k].size()) ? std::numeric_limits<int>::max() : pos_y[k][u];
        }
        template <typename Pred, constraints_t<std::is_invocable_r<bool, Pred, T>> = nullptr>
        int min_down(int k, int u, const Pred &f) const {
            const int d = data[k].min_left(comp_y(k, u), f);
            return d == 0 ? std::numeric_limits<int>::min() : pos_y[k][d - 1] + 1;
        }

        void update(int k, int y) {
            int p = comp_y(k, y);
            assert(pos_y[k][p] == y);
            if (k < m) {
                int l = comp_y(k * 2, y), r = comp_y(k * 2 + 1, y);
                T lv = pos_y[k * 2 + 0][l] == y ? data[k * 2 + 0].get(l) : e();
                T rv = pos_y[k * 2 + 1][r] == y ? data[k * 2 + 1].get(r) : e();
                data[k][p] = op(lv, rv);
            } else {
                data[k][p] = T(data[k][p]);
            }
        }
        void update_from(int k, int y) {
            for (; k; k >>= 1) update(k, y);
        }
};

} // namespace suisen
Back to top page