spl
This documentation is automatically generated by online-judge-tools/verification-helper
data_structure/test/rectangle_sum_range_tree.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
Code
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"
#define FAST_IO
#include "../../data_structure/operations.hpp"
#include "../../data_structure/range_tree.hpp"
#include "../../template/template.hpp"
int main() {
i32 n, q;
cin >> n >> q;
V<tuple<i32, i32, i64>> pts(n);
for (auto &[x, y, w] : pts) {
cin >> x >> y >> w;
}
RangeTree<i32, Add<i64>> range_tree(pts);
REP(qi, q) {
i32 l, d, r, u;
cin >> l >> d >> r >> u;
cout << range_tree.sum(l, r, d, u) << '\n';
}
}#line 1 "data_structure/test/rectangle_sum_range_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"
#define FAST_IO
#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 2 "data_structure/range_tree.hpp"
#line 4 "data_structure/range_tree.hpp"
#include <vector>
#include <tuple>
template <typename Coordinate, typename CommutativeGroup>
class RangeTree {
public:
using Value = typename CommutativeGroup::Value;
private:
struct Node {
std::vector<Coordinate> ys;
std::vector<Value> cum;
Value sum(Coordinate yl, Coordinate yr) const {
int yli =
(int)(std::lower_bound(ys.begin(), ys.end(), yl) - ys.begin());
int yri =
(int)(std::lower_bound(ys.begin(), ys.end(), yr) - ys.begin());
return CommutativeGroup::op(CommutativeGroup::inv(cum[yli]),
cum[yri]);
}
};
static void dedup(std::vector<Coordinate> &xs) {
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
}
static int index(const std::vector<Coordinate> &xs, int x) {
return (int)(std::lower_bound(xs.begin(), xs.end(), x) - xs.begin());
}
std::vector<Node> nodes;
std::vector<Coordinate> xs;
public:
RangeTree(const std::vector<std::tuple<Coordinate, Coordinate, Value>> &pts)
: nodes(), xs() {
xs.reserve(pts.size());
for (const auto &[x, _y, _w] : pts) {
xs.push_back(x);
}
dedup(xs);
nodes.resize(xs.size());
for (const auto &[x, y, _w] : pts) {
int xi = index(xs, x);
for (; xi < (int)xs.size(); xi |= xi + 1) {
nodes[xi].ys.push_back(y);
}
}
for (Node &node : nodes) {
dedup(node.ys);
node.cum.resize(node.ys.size() + 1, CommutativeGroup::id());
}
for (const auto &[x, y, w] : pts) {
int xi = index(xs, x);
for (; xi < (int)xs.size(); xi |= xi + 1) {
int yi = index(nodes[xi].ys, y);
nodes[xi].cum[yi + 1] =
CommutativeGroup::op(nodes[xi].cum[yi + 1], w);
}
}
for (Node &node : nodes) {
for (int i = 1; i < (int)node.cum.size(); ++i) {
node.cum[i] =
CommutativeGroup::op(node.cum[i - 1], node.cum[i]);
}
}
}
Value sum(Coordinate xr, Coordinate yl, Coordinate yr) const {
int xri = index(xs, xr);
Value s = CommutativeGroup::id();
for (; xri > 0; xri &= xri - 1) {
s = CommutativeGroup::op(s, nodes[xri - 1].sum(yl, yr));
}
return s;
}
Value sum(Coordinate xl, Coordinate xr, Coordinate yl,
Coordinate yr) const {
Value l = sum(xl, yl, yr), r = sum(xr, yl, yr);
return CommutativeGroup::op(r, CommutativeGroup::inv(l));
}
};
#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 7 "data_structure/test/rectangle_sum_range_tree.test.cpp"
int main() {
i32 n, q;
cin >> n >> q;
V<tuple<i32, i32, i64>> pts(n);
for (auto &[x, y, w] : pts) {
cin >> x >> y >> w;
}
RangeTree<i32, Add<i64>> range_tree(pts);
REP(qi, q) {
i32 l, d, r, u;
cin >> l >> d >> r >> u;
cout << range_tree.sum(l, r, d, u) << '\n';
}
}