cp-library-cpp

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

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

:heavy_check_mark: test/src/datastructure/fenwick_tree/persistent_fenwick_tree/rectangle_sum.test.cpp

Depends on

Code

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

#include <iostream>
#include <tuple>

#include "library/util/coordinate_compressor.hpp"
#include "library/datastructure/fenwick_tree/persistent_fenwick_tree.hpp"

using suisen::CoordinateCompressorBuilder;
using suisen::PersistentFenwickTree;

using Tree = PersistentFenwickTree<long long>;

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

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

    std::vector<std::tuple<int, int, int>> points(n);
    CoordinateCompressorBuilder<int> bx, by;

    for (auto &[x, y, w] : points) {
        std::cin >> x >> y >> w;
        bx.push(x);
        by.push(y);
    }
    auto cmp_x = bx.build(), cmp_y = by.build();

    const int h = cmp_x.size(), w = cmp_y.size();

    std::vector<std::vector<std::pair<int, int>>> buckets(h);
    for (auto &[x, y, w] : points) {
        x = cmp_x[x];
        y = cmp_y[y];
        buckets[x].emplace_back(y, w);
    }

    Tree::init_pool(5000000);

    std::vector<Tree> fts(h + 1);
    fts[0] = Tree(w);

    for (int x = 0; x < h; ++x) {
        fts[x + 1] = fts[x];
        for (const auto &[y, w] : buckets[x]) {
            fts[x + 1] = fts[x + 1].add(y, w);
        }
    }

    for (int query_id = 0; query_id < q; ++query_id) {
        int l, r, d, u;
        std::cin >> l >> d >> r >> u;

        l = cmp_x.min_geq_index(l);
        r = cmp_x.min_geq_index(r);
        d = cmp_y.min_geq_index(d);
        u = cmp_y.min_geq_index(u);

        std::cout << fts[r].sum(d, u) - fts[l].sum(d, u) << '\n';
    }

    return 0;
}
#line 1 "test/src/datastructure/fenwick_tree/persistent_fenwick_tree/rectangle_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"

#include <iostream>
#include <tuple>

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



#include <algorithm>
#include <cassert>
#include <vector>

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



#include <limits>
#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/util/coordinate_compressor.hpp"

namespace suisen {
template <typename T>
class CoordinateCompressorBuilder {
    public:
        struct Compressor {
            public:
                static constexpr int absent = -1;

                // default constructor
                Compressor() : _xs(std::vector<T>{}) {}
                // Construct from strictly sorted vector
                Compressor(const std::vector<T> &xs) : _xs(xs) {
                    assert(is_strictly_sorted(xs));
                }

                // Return the number of distinct keys.
                int size() const {
                    return _xs.size();
                }
                // Check if the element is registered.
                bool has_key(const T &e) const {
                    return std::binary_search(_xs.begin(), _xs.end(), e);
                }
                // Compress the element. if not registered, returns `default_value`. (default: Compressor::absent)
                int comp(const T &e, int default_value = absent) const {
                    const int res = min_geq_index(e);
                    return res != size() and _xs[res] == e ? res : default_value;
                }
                // Restore the element from the index.
                T decomp(const int compressed_index) const {
                    return _xs[compressed_index];
                }
                // Compress the element. Equivalent to call `comp(e)`
                int operator[](const T &e) const {
                    return comp(e);
                }
                // Return the minimum registered value greater than `e`. if not exists, return `default_value`.
                T min_gt(const T &e, const T &default_value) const {
                    auto it = std::upper_bound(_xs.begin(), _xs.end(), e);
                    return it == _xs.end() ? default_value : *it;
                }
                // Return the minimum registered value greater than or equal to `e`. if not exists, return `default_value`.
                T min_geq(const T &e, const T &default_value) const {
                    auto it = std::lower_bound(_xs.begin(), _xs.end(), e);
                    return it == _xs.end() ? default_value : *it;
                }
                // Return the maximum registered value less than `e`. if not exists, return `default_value`
                T max_lt(const T &e, const T &default_value) const {
                    auto it = std::upper_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>());
                    return it == _xs.rend() ? default_value : *it;
                }
                // Return the maximum registered value less than or equal to `e`. if not exists, return `default_value`
                T max_leq(const T &e, const T &default_value) const {
                    auto it = std::lower_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>());
                    return it == _xs.rend() ? default_value : *it;
                }
                // Return the compressed index of the minimum registered value greater than `e`. if not exists, return `compressor.size()`.
                int min_gt_index(const T &e) const {
                    return std::upper_bound(_xs.begin(), _xs.end(), e) - _xs.begin();
                }
                // Return the compressed index of the minimum registered value greater than or equal to `e`. if not exists, return `compressor.size()`.
                int min_geq_index(const T &e) const {
                    return std::lower_bound(_xs.begin(), _xs.end(), e) - _xs.begin();
                }
                // Return the compressed index of the maximum registered value less than `e`. if not exists, return -1.
                int max_lt_index(const T &e) const {
                    return int(_xs.rend() - std::upper_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>())) - 1;
                }
                // Return the compressed index of the maximum registered value less than or equal to `e`. if not exists, return -1.
                int max_leq_index(const T &e) const {
                    return int(_xs.rend() - std::lower_bound(_xs.rbegin(), _xs.rend(), e, std::greater<T>())) - 1;
                }
            private:
                std::vector<T> _xs;
                static bool is_strictly_sorted(const std::vector<T> &v) {
                    return std::adjacent_find(v.begin(), v.end(), std::greater_equal<T>()) == v.end();
                }
        };
        CoordinateCompressorBuilder() : _xs(std::vector<T>{}) {}
        explicit CoordinateCompressorBuilder(const std::vector<T> &xs) : _xs(xs) {}
        explicit CoordinateCompressorBuilder(std::vector<T> &&xs) : _xs(std::move(xs)) {}
        template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr>
        CoordinateCompressorBuilder(const int n, Gen generator) {
            reserve(n);
            for (int i = 0; i < n; ++i) push(generator(i));
        }
        // Attempt to preallocate enough memory for specified number of elements.
        void reserve(int n) {
            _xs.reserve(n);
        }
        // Add data.
        void push(const T &first) {
            _xs.push_back(first);
        }
        // Add data.
        void push(T &&first) {
            _xs.push_back(std::move(first));
        }
        // Add data in the range of [first, last). 
        template <typename Iterator>
        auto push(const Iterator &first, const Iterator &last) -> decltype(std::vector<T>{}.push_back(*first), void()) {
            for (auto it = first; it != last; ++it) _xs.push_back(*it);
        }
        // Add all data in the container. Equivalent to `push(iterable.begin(), iterable.end())`.
        template <typename Iterable>
        auto push(const Iterable &iterable) -> decltype(std::vector<T>{}.push_back(*iterable.begin()), void()) {
            push(iterable.begin(), iterable.end());
        }
        // Add data.
        template <typename ...Args>
        void emplace(Args &&...args) {
            _xs.emplace_back(std::forward<Args>(args)...);
        }
        // Build compressor.
        auto build() {
            std::sort(_xs.begin(), _xs.end()), _xs.erase(std::unique(_xs.begin(), _xs.end()), _xs.end());
            return Compressor {_xs};
        }
        // Build compressor from vector.
        static auto build(const std::vector<T> &xs) {
            return CoordinateCompressorBuilder(xs).build();
        }
        // Build compressor from vector.
        static auto build(std::vector<T> &&xs) {
            return CoordinateCompressorBuilder(std::move(xs)).build();
        }
        // Build compressor from generator.
        template <typename Gen, constraints_t<std::is_invocable_r<T, Gen, int>> = nullptr>
        static auto build(const int n, Gen generator) {
            return CoordinateCompressorBuilder<T>(n, generator).build();
        }
    private:
        std::vector<T> _xs;
};

} // namespace suisen


#line 1 "library/datastructure/fenwick_tree/persistent_fenwick_tree.hpp"



#line 5 "library/datastructure/fenwick_tree/persistent_fenwick_tree.hpp"

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



#include <deque>
#line 6 "library/util/object_pool.hpp"

namespace suisen {
    template <typename T, bool auto_extend = false>
    struct ObjectPool {
        using value_type = T;
        using value_pointer_type = T*;

        template <typename U>
        using container_type = std::conditional_t<auto_extend, std::deque<U>, std::vector<U>>;

        container_type<value_type> pool;
        container_type<value_pointer_type> stock;
        decltype(stock.begin()) it;

        ObjectPool() : ObjectPool(0) {}
        ObjectPool(int size) : pool(size), stock(size) {
            clear();
        }

        int capacity() const { return pool.size(); }
        int size() const { return it - stock.begin(); }

        value_pointer_type alloc() {
            if constexpr (auto_extend) ensure();
            return *it++;
        }

        void free(value_pointer_type t) {
            *--it = t;
        }

        void clear() {
            int size = pool.size();
            it = stock.begin();
            for (int i = 0; i < size; i++) stock[i] = &pool[i];
        }

        void ensure() {
            if (it != stock.end()) return;
            int size = stock.size();
            for (int i = size; i <= size * 2; ++i) {
                stock.push_back(&pool.emplace_back());
            }
            it = stock.begin() + size;
        }
    };
} // namespace suisen


#line 7 "library/datastructure/fenwick_tree/persistent_fenwick_tree.hpp"

namespace suisen {
    template <typename T>
    struct PersistentFenwickTree {
        struct Node;

        using value_type = T;

        using node_type = Node;
        using node_pointer_type = node_type*;

        struct Node {
            static inline ObjectPool<node_type> _pool;

            node_pointer_type _ch[2]{ nullptr, nullptr };
            value_type _dat;

            Node() : _dat{} {}

            static node_pointer_type clone(node_pointer_type node) {
                return &(*_pool.alloc() = *node);
            }

            static node_pointer_type build(const std::vector<value_type> &dat, int p) {
                const int n = dat.size();
                std::vector<node_pointer_type> nodes(n + 1);
                auto rec = [&](auto rec, int p, int id) -> node_pointer_type {
                    if (p == 0) return nullptr;
                    const int np = p >> 1;
                    node_pointer_type res = _pool.alloc();
                    res->_ch[0] = rec(rec, np, id - np);
                    if (id + 1 <= n) res->_ch[1] = rec(rec, np, id + np);
                    if (id <= n) nodes[id] = res;
                    return res;
                };
                node_pointer_type res = rec(rec, p, p);
                for (int i = 1; i <= n; ++i) {
                    int par = i + (i & -i);
                    if (par <= n) nodes[par]->_dat += nodes[i]->_dat;
                }
                return res;
            }

            static value_type sum(node_pointer_type node, int p, int l, int r) {
                return sum(node, p, r) - sum(node, p, l);
            }

            static node_pointer_type add(node_pointer_type node, int p, int i, const value_type& val) {
                ++i;
                node_pointer_type res = clone(node);
                for (node_pointer_type cur = res;; p >>= 1) {
                    if (i & p) {
                        if (i ^= p) {
                            cur = cur->_ch[1] = clone(cur->_ch[1]);
                        } else {
                            cur->_dat += val;
                            return res;
                        }
                    } else {
                        cur->_dat += val;
                        cur = cur->_ch[0] = clone(cur->_ch[0]);
                    }
                }
            }
        private:
            static value_type sum(node_pointer_type node, int p, int r) {
                value_type res{};
                for (; r; p >>= 1) {
                    if (r & p) {
                        r ^= p;
                        res += node->_dat;
                        node = node->_ch[1];
                    } else {
                        node = node->_ch[0];
                    }
                }
                return res;
            }
        };

        PersistentFenwickTree() : _p(0), _root(nullptr) {}
        explicit PersistentFenwickTree(int n) : PersistentFenwickTree(std::vector<value_type>(n, T{})) {}
        PersistentFenwickTree(const std::vector<value_type>& dat) : _p(floor_pow2(dat.size())), _root(node_type::build(dat, _p)) {}

        static void init_pool(int size) {
            node_type::_pool = ObjectPool<node_type>(size);
        }
        static void clear_pool() {
            node_type::_pool.clear();
        }

        value_type sum(int l, int r) {
            return node_type::sum(_root, _p, l, r);
        }
        PersistentFenwickTree add(int i, const value_type &val) {
            return PersistentFenwickTree(_p, node_type::add(_root, _p, i, val));
        }

    private:
        int _p;
        node_pointer_type _root;
        PersistentFenwickTree(int p, node_pointer_type root) : _p(p), _root(root) {}

        static constexpr int floor_pow2(int n) {
            int x = 31 - __builtin_clz(n);
            return x < 0 ? 0 : 1 << x;
        }
    };
}


#line 8 "test/src/datastructure/fenwick_tree/persistent_fenwick_tree/rectangle_sum.test.cpp"

using suisen::CoordinateCompressorBuilder;
using suisen::PersistentFenwickTree;

using Tree = PersistentFenwickTree<long long>;

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

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

    std::vector<std::tuple<int, int, int>> points(n);
    CoordinateCompressorBuilder<int> bx, by;

    for (auto &[x, y, w] : points) {
        std::cin >> x >> y >> w;
        bx.push(x);
        by.push(y);
    }
    auto cmp_x = bx.build(), cmp_y = by.build();

    const int h = cmp_x.size(), w = cmp_y.size();

    std::vector<std::vector<std::pair<int, int>>> buckets(h);
    for (auto &[x, y, w] : points) {
        x = cmp_x[x];
        y = cmp_y[y];
        buckets[x].emplace_back(y, w);
    }

    Tree::init_pool(5000000);

    std::vector<Tree> fts(h + 1);
    fts[0] = Tree(w);

    for (int x = 0; x < h; ++x) {
        fts[x + 1] = fts[x];
        for (const auto &[y, w] : buckets[x]) {
            fts[x + 1] = fts[x + 1].add(y, w);
        }
    }

    for (int query_id = 0; query_id < q; ++query_id) {
        int l, r, d, u;
        std::cin >> l >> d >> r >> u;

        l = cmp_x.min_geq_index(l);
        r = cmp_x.min_geq_index(r);
        d = cmp_y.min_geq_index(d);
        u = cmp_y.min_geq_index(u);

        std::cout << fts[r].sum(d, u) - fts[l].sum(d, u) << '\n';
    }

    return 0;
}
Back to top page