This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum" // header file section #include <algorithm> #include <bitset> #include <cfloat> #include <cstdio> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <tuple> #include <vector> #include "../../segment_tree/persistent_segment_tree.hpp" #include "../../util/coordinate_compression.hpp" using namespace std; using llong = long long; struct Monoid { using value_type = llong; static llong operation(llong a, llong b) { return a + b; }; static llong identity() { return 0; } }; llong n, q; vector<PersistentSegmentTree<Monoid>> v; vector<tuple<llong, llong, llong>> p; CoordinateCompressionBuilder<llong> x_axis_builder; CoordinateCompressionBuilder<llong> y_axis_builder; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> q; for (int i = 0; i < n; i++) { llong x, y, w; cin >> x >> y >> w; p.push_back(tie(y, x, w)); x_axis_builder.push(x); y_axis_builder.push(y); } sort(p.begin(), p.end()); auto x_axis = x_axis_builder.build(); auto y_axis = y_axis_builder.build(); v.push_back(PersistentSegmentTree<Monoid>(x_axis.size())); for (int i = 0; i < p.size(); i++) { llong x, y, w; tie(y, x, w) = p[i]; x = x_axis.zip(x); y = y_axis.zip(y); if (v.size() <= y) { v.push_back(v[y - 1]); } v[y] = v[y].update(x, v[y][x] + w); } for (int i = 0; i < q; i++) { llong l, d, r, u; cin >> l >> d >> r >> u; l = x_axis.zip(l); r = x_axis.zip(r); d = y_axis.zip(d) - 1; u = y_axis.zip(u) - 1; if (d >= 0) cout << v[u].fold(l, r) - v[d].fold(l, r) << '\n'; else if (u >= 0) cout << v[u].fold(l, r) << '\n'; else cout << 0 << '\n'; } return 0; };
#line 1 "test/yosupo/rectangle_sum1.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum" // header file section #include <algorithm> #include <bitset> #include <cfloat> #include <cstdio> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <tuple> #include <vector> #line 1 "segment_tree/persistent_segment_tree.hpp" #include <cstddef> #include <cstdint> #line 7 "segment_tree/persistent_segment_tree.hpp" #include <iterator> #line 9 "segment_tree/persistent_segment_tree.hpp" template <class Monoid> struct PersistentSegmentTree { using uint = size_t; using T = typename Monoid::value_type; struct Node { T dat; Node *l = nullptr, *r = nullptr; Node(T dat) : dat(dat){}; }; Node *root; uint n; Node *merge_node(Node *lch, Node *rch) { T l = (lch ? lch->dat : Monoid::identity()); T r = (rch ? rch->dat : Monoid::identity()); Node *ret = new Node(Monoid::operation(l, r)); ret->l = lch; ret->r = rch; return ret; }; PersistentSegmentTree(const PersistentSegmentTree &) = default; PersistentSegmentTree &operator=(const PersistentSegmentTree &) = default; PersistentSegmentTree(uint n, Node *r) : root(r), n(n){}; PersistentSegmentTree(uint n) : root(alloc(0, n, std::vector<T>(n, Monoid::identity()))), n(n){}; template <class InputItr> PersistentSegmentTree(const InputItr first, const InputItr last) : n(std::distance(first, last)), root(alloc(0, n, std::vector<T>(first, last))){}; Node *alloc(uint nl, uint nr, const std::vector<T> &v) { if (nr - nl <= 1) return new Node(v[nl]); else return merge_node(alloc(nl, (nl + nr) / 2, v), alloc((nl + nr) / 2, nr, v)); }; const T fold(uint l, uint r) const { return fold(l, r, 0, n, root); }; const T fold(uint ql, uint qr, uint nl, uint nr, const Node *np) const { if (np == nullptr || qr <= nl || nr <= ql) return Monoid::identity(); else if (ql <= nl && nr <= qr) return np->dat; else return Monoid::operation(fold(ql, qr, nl, (nl + nr) / 2, np->l), fold(ql, qr, (nl + nr) / 2, nr, np->r)); }; PersistentSegmentTree update(uint idx, T d) { return set(idx, d); }; PersistentSegmentTree set(uint idx, T d) { return PersistentSegmentTree(n, update(0, n, idx, d, root)); }; Node *update(uint nl, uint nr, uint idx, T d, Node *np) { if (idx < nl || nr <= idx) return np; else if (nr - nl == 1) return new Node(d); else return merge_node(update(nl, (nl + nr) / 2, idx, d, np->l), update((nl + nr) / 2, nr, idx, d, np->r)); }; PersistentSegmentTree get_tree() { return *this; }; T operator[](uint idx) { return fold(idx, idx + 1, 0, n, root); }; }; #line 1 "util/coordinate_compression.hpp" #line 5 "util/coordinate_compression.hpp" template <class T> struct CoordinateCompression { std::vector<T> p; template <class InputItr> CoordinateCompression(InputItr first, InputItr last) : p(first, last) { std::sort(p.begin(), p.end()); p.erase(unique(p.begin(), p.end()), p.end()); }; int zip(T x) { return std::lower_bound(p.begin(), p.end(), x) - p.begin(); }; T unzip(int x) { return p[x]; }; int size() { return p.size(); }; }; template <class T> struct CoordinateCompressionBuilder { std::vector<T> p; CoordinateCompressionBuilder() = default; template <class InputItr> CoordinateCompressionBuilder(InputItr first, InputItr last) : p(first, last){}; void push(T x) { p.push_back(x); }; CoordinateCompression<T> build() { return CoordinateCompression<T>(p.begin(), p.end()); }; }; #line 19 "test/yosupo/rectangle_sum1.test.cpp" using namespace std; using llong = long long; struct Monoid { using value_type = llong; static llong operation(llong a, llong b) { return a + b; }; static llong identity() { return 0; } }; llong n, q; vector<PersistentSegmentTree<Monoid>> v; vector<tuple<llong, llong, llong>> p; CoordinateCompressionBuilder<llong> x_axis_builder; CoordinateCompressionBuilder<llong> y_axis_builder; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> q; for (int i = 0; i < n; i++) { llong x, y, w; cin >> x >> y >> w; p.push_back(tie(y, x, w)); x_axis_builder.push(x); y_axis_builder.push(y); } sort(p.begin(), p.end()); auto x_axis = x_axis_builder.build(); auto y_axis = y_axis_builder.build(); v.push_back(PersistentSegmentTree<Monoid>(x_axis.size())); for (int i = 0; i < p.size(); i++) { llong x, y, w; tie(y, x, w) = p[i]; x = x_axis.zip(x); y = y_axis.zip(y); if (v.size() <= y) { v.push_back(v[y - 1]); } v[y] = v[y].update(x, v[y][x] + w); } for (int i = 0; i < q; i++) { llong l, d, r, u; cin >> l >> d >> r >> u; l = x_axis.zip(l); r = x_axis.zip(r); d = y_axis.zip(d) - 1; u = y_axis.zip(u) - 1; if (d >= 0) cout << v[u].fold(l, r) - v[d].fold(l, r) << '\n'; else if (u >= 0) cout << v[u].fold(l, r) << '\n'; else cout << 0 << '\n'; } return 0; };