sotanishy's competitive programming library

sotanishy's code snippets for competitive programming

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

:heavy_check_mark: test/yosupo/point_add_rectangle_sum.quadtree.test.cpp

Depends on

Code

#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";
        }
    }
}
Back to top page