sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum" #include <bits/stdc++.h> #include "../../data-structure/quadtree.hpp" #include "../../misc/compress.hpp" using namespace std; using ll = long long; struct AddMonoid { using T = ll; static T id() { return 0; } static T op(T a, T b) { return a + b; } }; struct Query { int t, x, y, w, l, d, r, u; Query(int t, int x, int y, int w) : t(t), x(x), y(y), w(w) {} Query(int t, int l, int d, int r, int u) : t(t), l(l), d(d), r(r), u(u) {} }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N >> Q; vector<int> xs, ys; vector<int> x(N), y(N), w(N); for (int i = 0; i < N; ++i) { cin >> x[i] >> y[i] >> w[i]; } xs.insert(xs.end(), x.begin(), x.end()); ys.insert(ys.end(), y.begin(), y.end()); vector<Query> queries; for (int i = 0; i < Q; ++i) { int t; cin >> t; if (t == 0) { int x, y, w; cin >> x >> y >> w; queries.emplace_back(t, x, y, w); xs.push_back(x); ys.push_back(y); } else { int l, d, r, u; cin >> l >> d >> r >> u; queries.emplace_back(t, l, d, r, u); xs.push_back(l); ys.push_back(d); xs.push_back(r); ys.push_back(u); } } Compress<int> cx(xs), cy(ys); x = cx.compress(x); y = cy.compress(y); Quadtree<AddMonoid> qt(xs.size()); for (int i = 0; i < N; ++i) { qt.update(x[i], y[i], qt.get(x[i], y[i]) + w[i]); } for (auto& q : queries) { if (q.t == 0) { int a = cx.compress(q.x), b = cy.compress(q.y); qt.update(a, b, qt.get(a, b) + q.w); } else { int l = cx.compress(q.l), r = cx.compress(q.r); int d = cy.compress(q.d), u = cy.compress(q.u); cout << qt.fold(l, r, d, u) << "\n"; } } }
#line 1 "test/yosupo/point_add_rectangle_sum.quadtree.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum" #include <bits/stdc++.h> #line 4 "data-structure/quadtree.hpp" template <typename M> class Quadtree { using T = M::T; public: Quadtree() = default; Quadtree(int n) : root(std::make_unique<Node>()) { size = 1; while (size < n) size <<= 1; } T get(int x, int y) const { return fold(x, x + 1, y, y + 1); } void update(int x, int y, const T& val) const { update(x, y, val, root, 0, 0, size); } T fold(int l, int r, int b, int t) const { return fold(l, r, b, t, root, 0, 0, size); } private: struct Node; using node_ptr = std::unique_ptr<Node>; struct Node { T val; node_ptr ch[4]; Node() : val(M::id()) {} }; const node_ptr root; int size; void update(int x, int y, const T& val, const node_ptr& n, int p, int q, int len) const { if (len == 1) { n->val = val; return; } len /= 2; for (int i = 3; i >= 0; --i) { if (x >= p + len * (i >> 1) && y >= q + len * (i & 1)) { if (!n->ch[i]) n->ch[i] = std::make_unique<Node>(); update(x, y, val, n->ch[i], p + len * (i >> 1), q + len * (i & 1), len); break; } } n->val = M::id(); for (int i = 0; i < 4; ++i) { if (n->ch[i]) n->val = M::op(n->val, n->ch[i]->val); } } T fold(int l, int r, int b, int t, const node_ptr& n, int p, int q, int len) const { if (!n) return M::id(); if (p + len <= l || r <= p || q + len <= b || t <= q) { return M::id(); } if (l <= p && p + len <= r && b <= q && q + len <= t) { return n->val; } len /= 2; T val = M::id(); for (int i = 0; i < 4; ++i) { if (n->ch[i]) val = M::op(val, fold(l, r, b, t, n->ch[i], p + len * (i >> 1), q + len * (i & 1), len)); } return val; } }; #line 4 "misc/compress.hpp" /** * @brief Coordinate Compression */ template <typename T> class Compress { public: Compress() = default; explicit Compress(const std::vector<T>& vs) : xs(vs) { std::ranges::sort(xs); xs.erase(std::ranges::unique(xs).begin(), xs.end()); } int compress(const T& x) const { return std::ranges::lower_bound(xs, x) - xs.begin(); } std::vector<int> compress(const std::vector<T>& vs) const { std::vector<int> res(vs.size()); std::ranges::transform(vs, res.begin(), [&](const T& x) { return compress(x); }); return res; } T decompress(int i) const { return xs[i]; } int size() const { return xs.size(); } private: std::vector<T> xs; }; #line 7 "test/yosupo/point_add_rectangle_sum.quadtree.test.cpp" using namespace std; using ll = long long; struct AddMonoid { using T = ll; static T id() { return 0; } static T op(T a, T b) { return a + b; } }; struct Query { int t, x, y, w, l, d, r, u; Query(int t, int x, int y, int w) : t(t), x(x), y(y), w(w) {} Query(int t, int l, int d, int r, int u) : t(t), l(l), d(d), r(r), u(u) {} }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, Q; cin >> N >> Q; vector<int> xs, ys; vector<int> x(N), y(N), w(N); for (int i = 0; i < N; ++i) { cin >> x[i] >> y[i] >> w[i]; } xs.insert(xs.end(), x.begin(), x.end()); ys.insert(ys.end(), y.begin(), y.end()); vector<Query> queries; for (int i = 0; i < Q; ++i) { int t; cin >> t; if (t == 0) { int x, y, w; cin >> x >> y >> w; queries.emplace_back(t, x, y, w); xs.push_back(x); ys.push_back(y); } else { int l, d, r, u; cin >> l >> d >> r >> u; queries.emplace_back(t, l, d, r, u); xs.push_back(l); ys.push_back(d); xs.push_back(r); ys.push_back(u); } } Compress<int> cx(xs), cy(ys); x = cx.compress(x); y = cy.compress(y); Quadtree<AddMonoid> qt(xs.size()); for (int i = 0; i < N; ++i) { qt.update(x[i], y[i], qt.get(x[i], y[i]) + w[i]); } for (auto& q : queries) { if (q.t == 0) { int a = cx.compress(q.x), b = cy.compress(q.y); qt.update(a, b, qt.get(a, b) + q.w); } else { int l = cx.compress(q.l), r = cx.compress(q.r); int d = cy.compress(q.d), u = cy.compress(q.u); cout << qt.fold(l, r, d, u) << "\n"; } } }