data_structure/test/rectangle_sum.test.cpp

• View this file on GitHub
• Last update: 2025-06-28 10:05:47+09:00
• Problem: https://judge.yosupo.jp/problem/rectangle_sum

Depends on

• data_structure/fenwick_tree.hpp
• data_structure/operations.hpp
• data_structure/rectangle_sum.hpp
• template/template.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"
#define FAST_IO

#include "../../data_structure/rectangle_sum.hpp"
#include "../../template/template.hpp"

int main() {
    I32(n, q);
    RectangleSum<i32, i64> rs;
    for (int i = 0; i < n; ++i) {
        I32(x, y, w);
        rs.add_point(x, y, w);
    }
    for (int i = 0; i < q; ++i) {
        I32(l, d, r, u);
        rs.add_query(l, r, d, u);
    }
    V<i64> ret = rs.solve();
    REP(i, q) {
        cout << ret[i] << '\n';
    }
}

#line 1 "data_structure/test/rectangle_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"
#define FAST_IO

#line 2 "data_structure/fenwick_tree.hpp"

#include <cassert>
#include <vector>
#line 2 "data_structure/operations.hpp"

#include <algorithm>
#include <limits>
#include <utility>

template <typename T>
struct Add {
    using Value = T;
    static Value id() { return T(0); }
    static Value op(const Value &lhs, const Value &rhs) { return lhs + rhs; }
    static Value inv(const Value &x) { return -x; }
};

template <typename T>
struct Mul {
    using Value = T;
    static Value id() { return Value(1); }
    static Value op(const Value &lhs, const Value &rhs) { return lhs * rhs; }
    static Value inv(const Value &x) { return Value(1) / x; }
};

template <typename T>
struct Min {
    static_assert(std::numeric_limits<T>::is_specialized);
    using Value = T;
    static Value id() { return std::numeric_limits<T>::max(); }
    static Value op(const Value &lhs, const Value &rhs) {
        return std::min(lhs, rhs);
    }
};

template <typename T>
struct Max {
    static_assert(std::numeric_limits<T>::is_specialized);
    using Value = T;
    static Value id() { return std::numeric_limits<Value>::min(); }
    static Value op(const Value &lhs, const Value &rhs) {
        return std::max(lhs, rhs);
    }
};

template <typename T>
struct Xor {
    using Value = T;
    static Value id() { return T(0); }
    static Value op(const Value &lhs, const Value &rhs) { return lhs ^ rhs; }
    static Value inv(const Value &x) { return x; }
};

template <typename Monoid>
struct Reversible {
    using Value = std::pair<typename Monoid::Value, typename Monoid::Value>;
    static Value id() { return Value(Monoid::id(), Monoid::id()); }
    static Value op(const Value &v1, const Value &v2) {
        return Value(Monoid::op(v1.first, v2.first),
                     Monoid::op(v2.second, v1.second));
    }
};
#line 6 "data_structure/fenwick_tree.hpp"

template <typename CommutativeGroup>
class FenwickTree {
public:
    using Value = typename CommutativeGroup::Value;

private:
    std::vector<Value> data;

public:
    FenwickTree(int n) : data(n, CommutativeGroup::id()) {}

    void add(int idx, const Value &x) {
        assert(idx >= 0 && idx < (int)data.size());
        for (; idx < (int)data.size(); idx |= idx + 1) {
            data[idx] = CommutativeGroup::op(data[idx], x);
        }
    }

    Value sum(int r) const {
        assert(r >= 0 && r <= (int)data.size());
        Value ret = CommutativeGroup::id();
        for (; r > 0; r &= r - 1) {
            ret = CommutativeGroup::op(ret, data[r - 1]);
        }
        return ret;
    }

    Value sum(int l, int r) const {
        assert(l >= 0 && l <= r && r <= (int)data.size());
        return CommutativeGroup::op(sum(r), CommutativeGroup::inv(sum(l)));
    }
};

template <typename T>
using FenwickTreeAdd = FenwickTree<Add<T>>;
#line 4 "data_structure/rectangle_sum.hpp"
template <typename C, typename V>
class RectangleSum {
    struct Point {
        C x, y;
        V v;
    };
    struct Query {
        C xl, xr, yl, yr;
        int idx;
    };
    std::vector<Point> pts;
    std::vector<Query> qrs;
public:
    RectangleSum() : pts(), qrs() {}
    void add_point(C x, C y, V v) {
        pts.emplace_back(Point{x, y, v});
    }
    void add_query(C xl, C xr, C yl, C yr) {
        qrs.emplace_back(Query{xl, xr, yl, yr, (int)qrs.size()});
    }
    std::vector<V> solve() {
        std::sort(pts.begin(), pts.end(), [](const Point &p0, const Point &p1) -> bool {
            return p0.x < p1.x;
        });
        struct Q {
            C x, d, u;
            int id;
            bool is_positive;
        };
        std::vector<Q> q_;
        q_.reserve(2 * qrs.size());
        for (const Query &qr : qrs) {
            q_.push_back(Q{qr.xl, qr.yl, qr.yr, qr.idx, false});
            q_.push_back(Q{qr.xr, qr.yl, qr.yr, qr.idx, true});
        }
        std::sort(q_.begin(), q_.end(), [](const Q &q0, const Q &q1) -> bool {
            return q0.x < q1.x;
        });
        std::vector<C> ys;
        ys.reserve(pts.size());
        for (const Point &p : pts) {
            ys.push_back(p.y);
        }
        std::sort(ys.begin(), ys.end());
        ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
        FenwickTreeAdd<V> fw((int)ys.size());
        std::vector<V> ret(qrs.size(), 0);
        typename std::vector<Point>::iterator it = pts.begin();
        for (const Q &q : q_) {
            while (it != pts.end() && it->x < q.x) {
                int y = (int)(std::lower_bound(ys.begin(), ys.end(), it->y) - ys.begin());
                fw.add(y, it->v);
                ++it;
            }
            int d = (int)(std::lower_bound(ys.begin(), ys.end(), q.d) - ys.begin());
            int u = (int)(std::lower_bound(ys.begin(), ys.end(), q.u) - ys.begin());
            V sum = fw.sum(d, u);
            if (q.is_positive) {
                ret[q.id] += sum;
            } else {
                ret[q.id] -= sum;
            }
        }
        return ret;
    }
};
#line 2 "template/template.hpp"
#include <bits/stdc++.h>
#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)
#define PER3(i, m, n) for (i32 i = (i32)(n)-1; i >= (i32)(m); --i)
#define PER(...) OVERRIDE(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define LEN(x) (i32)(x.size())
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
using i32 = signed int;
using i64 = signed long long;
using f64 = double;
using f80 = long double;
using pi = pair<i32, i32>;
using pl = pair<i64, i64>;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
template <typename T>
using VVV = V<V<V<T>>>;
template <typename T>
using VVVV = V<V<V<V<T>>>>;
template <typename T>
using PQR = priority_queue<T, V<T>, greater<T>>;
template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
i32 lob(const V<T> &arr, const T &v) {
    return (i32)(lower_bound(ALL(arr), v) - arr.begin());
}
template <typename T>
i32 upb(const V<T> &arr, const T &v) {
    return (i32)(upper_bound(ALL(arr), v) - arr.begin());
}
template <typename T>
V<i32> argsort(const V<T> &arr) {
    V<i32> ret(arr.size());
    iota(ALL(ret), 0);
    sort(ALL(ret), [&](i32 i, i32 j) -> bool {
        if (arr[i] == arr[j]) {
            return i < j;
        } else {
            return arr[i] < arr[j];
        }
    });
    return ret;
}
#ifdef INT128
using u128 = __uint128_t;
using i128 = __int128_t;
#endif
[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;
struct SetUpIO {
    SetUpIO() {
#ifdef FAST_IO
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
#endif
        cout << fixed << setprecision(15);
    }
} set_up_io;
void scan(char &x) { cin >> x; }
void scan(u32 &x) { cin >> x; }
void scan(u64 &x) { cin >> x; }
void scan(i32 &x) { cin >> x; }
void scan(i64 &x) { cin >> x; }
void scan(f64 &x) { cin >> x; }
void scan(string &x) { cin >> x; }
template <typename T>
void scan(V<T> &x) {
    for (T &ele : x) {
        scan(ele);
    }
}
void read() {}
template <typename Head, typename... Tail>
void read(Head &head, Tail &...tail) {
    scan(head);
    read(tail...);
}
#define CHAR(...)     \
    char __VA_ARGS__; \
    read(__VA_ARGS__);
#define U32(...)     \
    u32 __VA_ARGS__; \
    read(__VA_ARGS__);
#define U64(...)     \
    u64 __VA_ARGS__; \
    read(__VA_ARGS__);
#define I32(...)     \
    i32 __VA_ARGS__; \
    read(__VA_ARGS__);
#define I64(...)     \
    i64 __VA_ARGS__; \
    read(__VA_ARGS__);
#define F64(...)     \
    f64 __VA_ARGS__; \
    read(__VA_ARGS__);
#define STR(...)        \
    string __VA_ARGS__; \
    read(__VA_ARGS__);
#define VEC(type, name, size) \
    V<type> name(size);       \
    read(name);
#define VVEC(type, name, size1, size2)    \
    VV<type> name(size1, V<type>(size2)); \
    read(name);
#line 6 "data_structure/test/rectangle_sum.test.cpp"

int main() {
    I32(n, q);
    RectangleSum<i32, i64> rs;
    for (int i = 0; i < n; ++i) {
        I32(x, y, w);
        rs.add_point(x, y, w);
    }
    for (int i = 0; i < q; ++i) {
        I32(l, d, r, u);
        rs.add_query(l, r, d, u);
    }
    V<i64> ret = rs.solve();
    REP(i, q) {
        cout << ret[i] << '\n';
    }
}

Back to top page