spl
This documentation is automatically generated by online-judge-tools/verification-helper
data_structure/test/point_add_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/point_add_rectangle_sum
Depends on
- data_structure/fenwick_tree.hpp
- data_structure/general_range_tree.hpp
- data_structure/operations.hpp
- template/template.hpp
Code
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum"
#define FAST_IO
#include "../../data_structure/fenwick_tree.hpp"
#include "../../data_structure/general_range_tree.hpp"
#include "../../template/template.hpp"
int main() {
i32 n, q;
cin >> n >> q;
V<i32> x(n), y(n), w(n);
REP(i, n) { cin >> x[i] >> y[i] >> w[i]; }
V<tuple<i32, i32, i32, i32, i32>> queries(q);
for (auto &[type, a, b, c, d] : queries) {
cin >> type;
if (type == 0) {
cin >> a >> b >> c;
d = 0;
} else {
cin >> a >> b >> c >> d;
}
}
i32 pct = n;
for (const auto &[type, _a, _b, _c, _d] : queries) {
if (type == 0) {
++pct;
}
}
V<pi> pts;
pts.reserve(pct);
REP(i, n) { pts.emplace_back(x[i], y[i]); }
for (const auto &[type, a, b, c, d] : queries) {
if (type == 0) {
pts.emplace_back(a, b);
}
}
GRangeTree rt(pts);
VV<i32> upd_pct(pct - n);
REP(i, rt.size()) {
if (rt[i] >= n) {
upd_pct[rt[i] - n].push_back(i);
}
}
FenwickTree<Add<i64>> ft(rt.size());
REP(i, rt.size()) {
if (rt[i] < n) {
ft.add(i, w[rt[i]]);
}
}
i32 it = 0;
for (const auto &[type, a, b, c, d] : queries) {
if (type == 0) {
for (i32 upd : upd_pct[it++]) {
ft.add(upd, c);
}
} else {
i64 ans = 0;
for (auto [l, r] : rt.rectangle(a, c, b, d)) {
ans += ft.sum(l, r);
}
cout << ans << '\n';
}
}
}#line 1 "data_structure/test/point_add_rectangle_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_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 2 "data_structure/general_range_tree.hpp"
#line 6 "data_structure/general_range_tree.hpp"
template <typename T>
class GRangeTree {
std::vector<T> xs;
std::vector<std::pair<T, int>> arr;
std::vector<int> rngs;
static bool compare_by_first(const std::pair<T, int> &p0,
const std::pair<T, int> &p1) {
return p0.first < p1.first;
}
public:
GRangeTree(const std::vector<std::pair<T, T>> &pts) : xs(), arr(), rngs() {
xs.reserve(pts.size());
for (const auto &[x, _y] : pts) {
xs.push_back(x);
}
std::sort(xs.begin(), xs.end());
xs.erase(std::unique(xs.begin(), xs.end()), xs.end());
int xs_sz = (int)xs.size();
std::vector<std::vector<std::pair<T, int>>> nodes(2 * xs_sz);
for (int i = 0; i < (int)pts.size(); ++i) {
int xi =
(int)(std::lower_bound(xs.begin(), xs.end(), pts[i].first) -
xs.begin());
nodes[xs_sz + xi].emplace_back(pts[i].second, i);
}
for (int i = xs_sz; i < 2 * xs_sz; ++i) {
std::sort(nodes[i].begin(), nodes[i].end(), compare_by_first);
}
for (int i = xs_sz - 1; i > 0; --i) {
nodes[i].reserve(nodes[2 * i].size() + nodes[2 * i + 1].size());
std::merge(nodes[2 * i].begin(), nodes[2 * i].end(),
nodes[2 * i + 1].begin(), nodes[2 * i + 1].end(),
std::back_inserter(nodes[i]), compare_by_first);
}
int tot = 0;
for (int i = 1; i < 2 * xs_sz; ++i) {
tot += (int)nodes[i].size();
}
arr.reserve(tot);
for (int i = 1; i < 2 * xs_sz; ++i) {
for (auto ele : nodes[i]) {
arr.emplace_back(ele);
}
}
rngs.resize(2 * xs_sz, 0);
for (int i = 1; i < 2 * xs_sz; ++i) {
rngs[i] = rngs[i - 1] + (int)nodes[i].size();
}
}
int size() const { return (int)arr.size(); }
int operator[](int i) const { return arr[i].second; }
// [xl, xr), [yl, yr)
std::vector<std::pair<int, int>> rectangle(T xl, T xr, T yl, T yr) const {
int xli =
(int)(std::lower_bound(xs.begin(), xs.end(), xl) - xs.begin());
int xri =
(int)(std::lower_bound(xs.begin(), xs.end(), xr) - xs.begin());
std::vector<std::pair<int, int>> ret;
xli += (int)xs.size();
xri += (int)xs.size();
while (xli < xri) {
if (xli % 2 == 1) {
int l = rngs[xli - 1];
int r = rngs[xli];
ret.emplace_back(
(int)(std::lower_bound(arr.begin() + l, arr.begin() + r,
std::pair<T, int>(yl, 0),
compare_by_first) -
arr.begin()),
(int)(std::lower_bound(arr.begin() + l, arr.begin() + r,
std::pair<T, int>(yr, 0),
compare_by_first) -
arr.begin()));
++xli;
}
if (xri % 2 == 1) {
--xri;
int l = rngs[xri - 1];
int r = rngs[xri];
ret.emplace_back(
(int)(std::lower_bound(arr.begin() + l, arr.begin() + r,
std::pair<T, int>(yl, 0),
compare_by_first) -
arr.begin()),
(int)(std::lower_bound(arr.begin() + l, arr.begin() + r,
std::pair<T, int>(yr, 0),
compare_by_first) -
arr.begin()));
}
xli /= 2;
xri /= 2;
}
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 7 "data_structure/test/point_add_rectangle_sum.test.cpp"
int main() {
i32 n, q;
cin >> n >> q;
V<i32> x(n), y(n), w(n);
REP(i, n) { cin >> x[i] >> y[i] >> w[i]; }
V<tuple<i32, i32, i32, i32, i32>> queries(q);
for (auto &[type, a, b, c, d] : queries) {
cin >> type;
if (type == 0) {
cin >> a >> b >> c;
d = 0;
} else {
cin >> a >> b >> c >> d;
}
}
i32 pct = n;
for (const auto &[type, _a, _b, _c, _d] : queries) {
if (type == 0) {
++pct;
}
}
V<pi> pts;
pts.reserve(pct);
REP(i, n) { pts.emplace_back(x[i], y[i]); }
for (const auto &[type, a, b, c, d] : queries) {
if (type == 0) {
pts.emplace_back(a, b);
}
}
GRangeTree rt(pts);
VV<i32> upd_pct(pct - n);
REP(i, rt.size()) {
if (rt[i] >= n) {
upd_pct[rt[i] - n].push_back(i);
}
}
FenwickTree<Add<i64>> ft(rt.size());
REP(i, rt.size()) {
if (rt[i] < n) {
ft.add(i, w[rt[i]]);
}
}
i32 it = 0;
for (const auto &[type, a, b, c, d] : queries) {
if (type == 0) {
for (i32 upd : upd_pct[it++]) {
ft.add(upd, c);
}
} else {
i64 ans = 0;
for (auto [l, r] : rt.rectangle(a, c, b, d)) {
ans += ft.sum(l, r);
}
cout << ans << '\n';
}
}
}