cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
test/src/datastructure/segment_tree/persistent_segment_tree/rectangle_sum.test.cpp
- View this file on GitHub
- Last update: 2026-06-19 20:35:33+09:00
- Problem: https://judge.yosupo.jp/problem/rectangle_sum
Depends on
- 永続セグメント木
(library/datastructure/segment_tree/persistent_segment_tree.hpp)
- Type Traits
(library/type_traits/type_traits.hpp)
- 座標圧縮
(library/util/coordinate_compressor.hpp)
- Object Pool
(library/util/object_pool.hpp)
Code
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"
#include <iostream>
#include <tuple>
#include "library/util/coordinate_compressor.hpp"
#include "library/datastructure/segment_tree/persistent_segment_tree.hpp"
long long op(long long x, long long y) {
return x + y;
}
long long e() {
return 0;
}
using suisen::CoordinateCompressorBuilder;
using suisen::PersistentSegmentTree;
using Tree = PersistentSegmentTree<long long, op, e>;
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 yw : buckets[x]) {
const int y = yw.first, w = yw.second;
fts[x + 1] = fts[x + 1].apply(y, [w](long long e) { return e + 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].prod(d, u) - fts[l].prod(d, u) << '\n';
}
return 0;
}#line 1 "test/src/datastructure/segment_tree/persistent_segment_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/segment_tree/persistent_segment_tree.hpp"
#line 5 "library/datastructure/segment_tree/persistent_segment_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/segment_tree/persistent_segment_tree.hpp"
namespace suisen {
template <typename T, T(*op)(T, T), T(*e)()>
struct PersistentSegmentTree {
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(e()) {}
static node_pointer_type clone(node_pointer_type node) {
return &(*_pool.alloc() = *node);
}
static void update(node_pointer_type node) {
node->_dat = op(node->_ch[0]->_dat, node->_ch[1]->_dat);
}
static bool is_leaf(node_pointer_type node) {
return not node->_ch[0];
}
static node_pointer_type build(const std::vector<value_type>& dat) {
auto rec = [&](auto rec, int l, int r) -> node_pointer_type {
node_pointer_type res = _pool.alloc();
if (r - l == 1) {
res->_dat = dat[l];
} else {
int m = (l + r) >> 1;
res->_ch[0] = rec(rec, l, m), res->_ch[1] = rec(rec, m, r);
update(res);
}
return res;
};
return rec(rec, 0, dat.size());
}
static value_type prod_all(node_pointer_type node) {
return node ? node->_dat : e();
}
static value_type prod(node_pointer_type node, int tl, int tr, int ql, int qr) {
if (tr <= ql or qr <= tl) return e();
if (ql <= tl and tr <= qr) return node->_dat;
int tm = (tl + tr) >> 1;
return op(prod(node->_ch[0], tl, tm, ql, qr), prod(node->_ch[1], tm, tr, ql, qr));
}
template <bool do_update, typename F>
static auto search_node(node_pointer_type node, int size, int i, F &&f) {
static std::vector<node_pointer_type> path;
node_pointer_type res = node;
if constexpr (do_update) res = clone(res);
node_pointer_type cur = res;
for (int l = 0, r = size; r - l > 1;) {
if constexpr (do_update) path.push_back(cur);
int m = (l + r) >> 1;
if (i < m) {
if constexpr (do_update) cur->_ch[0] = clone(cur->_ch[0]);
cur = cur->_ch[0];
r = m;
} else {
if constexpr (do_update) cur->_ch[1] = clone(cur->_ch[1]);
cur = cur->_ch[1];
l = m;
}
}
f(cur);
if constexpr (do_update) {
while (path.size()) update(path.back()), path.pop_back();
return res;
} else {
return;
}
}
static value_type get(node_pointer_type node, int size, int i) {
value_type res;
search_node</* do_update = */false>(node, size, i, [&](node_pointer_type i_th_node) { res = i_th_node->_dat; });
return res;
}
template <typename F>
static node_pointer_type apply(node_pointer_type node, int size, int i, F&& f) {
return search_node</* do_update = */true>(node, size, i, [&](node_pointer_type i_th_node) { i_th_node->_dat = f(i_th_node->_dat); });
}
static node_pointer_type set(node_pointer_type node, int size, int i, const value_type& dat) {
return apply(node, size, i, [&](const value_type&) { return dat; });
}
template <typename F>
static int max_right(node_pointer_type node, int size, int l, F&& f) {
assert(f(e()));
auto rec = [&](auto rec, node_pointer_type cur, int tl, int tr, value_type& sum) -> int {
if (tr <= l) return tr;
if (l <= tl) {
value_type nxt_sum = op(sum, cur->_dat);
if (f(nxt_sum)) {
sum = std::move(nxt_sum);
return tr;
}
if (tr - tl == 1) return tl;
}
int tm = (tl + tr) >> 1;
int res_l = rec(rec, cur->_ch[0], tl, tm, sum);
return res_l != tm ? res_l : rec(rec, cur->_ch[1], tm, tr, sum);
};
value_type sum = e();
return rec(rec, node, 0, size, sum);
}
template <typename F>
static int min_left(node_pointer_type node, int size, int r, F&& f) {
assert(f(e()));
auto rec = [&](auto rec, node_pointer_type cur, int tl, int tr, value_type& sum) -> int {
if (r <= tl) return tl;
if (tr <= r) {
value_type nxt_sum = op(cur->_dat, sum);
if (f(nxt_sum)) {
sum = std::move(nxt_sum);
return tl;
}
if (tr - tl == 1) return tr;
}
int tm = (tl + tr) >> 1;
int res_r = rec(rec, cur->_ch[1], tm, tr, sum);
return res_r != tm ? res_r : rec(rec, cur->_ch[0], tl, tm, sum);
};
value_type sum = e();
return rec(rec, node, 0, size, sum);
}
template <typename OutputIterator>
static void dump(node_pointer_type node, OutputIterator it) {
if (not node) return;
auto rec = [&](auto rec, node_pointer_type cur) -> void {
if (is_leaf(cur)) {
*it++ = cur->_dat;
} else {
rec(rec, cur->_ch[0]), rec(rec, cur->_ch[1]);
}
};
rec(rec, node);
}
static std::vector<value_type> dump(node_pointer_type node) {
std::vector<value_type> res;
dump(node, std::back_inserter(res));
return res;
}
};
PersistentSegmentTree() : _n(0), _root(nullptr) {}
explicit PersistentSegmentTree(int n) : PersistentSegmentTree(std::vector<value_type>(n, e())) {}
PersistentSegmentTree(const std::vector<value_type>& dat) : _n(dat.size()), _root(node_type::build(dat)) {}
static void init_pool(int size) {
node_type::_pool = ObjectPool<node_type>(size);
}
static void clear_pool() {
node_type::_pool.clear();
}
value_type prod_all() {
return node_type::prod_all(_root);
}
value_type prod(int l, int r) {
assert(0 <= l and l <= r and r <= _n);
return node_type::prod(_root, 0, _n, l, r);
}
value_type operator()(int l, int r) {
return prod(l, r);
}
value_type get(int i) {
assert(0 <= i and i < _n);
return node_type::get(_root, _n, i);
}
value_type operator[](int i) {
return get(i);
}
template <typename F>
PersistentSegmentTree apply(int i, F&& f) {
assert(0 <= i and i < _n);
return PersistentSegmentTree(_n, node_type::apply(_root, _n, i, std::forward<F>(f)));
}
PersistentSegmentTree set(int i, const value_type& v) {
assert(0 <= i and i < _n);
return PersistentSegmentTree(_n, node_type::set(_root, _n, i, v));
}
template <typename F>
int max_right(int l, F&& f) {
assert(0 <= l and l <= _n);
return node_type::max_right(_root, _n, l, std::forward<F>(f));
}
template <bool(*pred)(value_type)>
static int max_right(int l) {
return max_right(l, pred);
}
template <typename F>
int min_left(int r, F&& f) {
assert(0 <= r and r <= _n);
return node_type::min_left(_root, _n, r, std::forward<F>(f));
}
template <bool(*pred)(value_type)>
static int min_left(int r) {
return min_left(r, pred);
}
template <typename OutputIterator>
void dump(OutputIterator it) {
node_type::dump(_root, it);
}
std::vector<value_type> dump() {
return node_type::dump(_root);
}
private:
int _n;
node_pointer_type _root;
PersistentSegmentTree(int n, node_pointer_type root) : _n(n), _root(root) {}
};
}
#line 8 "test/src/datastructure/segment_tree/persistent_segment_tree/rectangle_sum.test.cpp"
long long op(long long x, long long y) {
return x + y;
}
long long e() {
return 0;
}
using suisen::CoordinateCompressorBuilder;
using suisen::PersistentSegmentTree;
using Tree = PersistentSegmentTree<long long, op, e>;
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 yw : buckets[x]) {
const int y = yw.first, w = yw.second;
fts[x + 1] = fts[x + 1].apply(y, [w](long long e) { return e + 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].prod(d, u) - fts[l].prod(d, u) << '\n';
}
return 0;
}