This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#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 siz) : pool(siz), stock(siz) { 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 siz = pool.size(); it = stock.begin(); for (int i = 0; i < siz; i++) stock[i] = &pool[i]; } void ensure() { if (it != stock.end()) return; int siz = stock.size(); for (int i = siz; i <= siz * 2; ++i) { stock.push_back(&pool.emplace_back()); } it = stock.begin() + siz; } }; } // 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 siz) { node_type::_pool = ObjectPool<node_type>(siz); } 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; }