This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum"
#include <bits/stdc++.h>
using namespace std;
#include "../../buffered_reader.h"
#include "../SegTree2D.h"
#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)
template<typename T>
struct Query {
static const int ADD = 0;
static const int QUERY = 1;
int typ; // ADD or QUERY
int x, y;
int x2, y2; // for QUERY: [x1, x2-1] * [y1, y2-1]
T weight;
};
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n = IO::get<int>();
int q = IO::get<int>();
using ll = long long;
vector<Query<ll>> queries;
REP(i,n) {
int x = IO::get<int>();
int y = IO::get<int>();
ll val = IO::get<ll>();
queries.push_back({Query<ll>::ADD, x, y, -1, -1, val});
}
REP(i,q) {
int typ = IO::get<int>();
if (typ == 0) {
int x = IO::get<int>();
int y = IO::get<int>();
ll val = IO::get<ll>();
queries.push_back({Query<ll>::ADD, x, y, -1, -1, val});
} else {
int x = IO::get<int>();
int y = IO::get<int>();
int x2 = IO::get<int>();
int y2 = IO::get<int>();
queries.push_back({Query<ll>::QUERY, x, y, x2, y2, 0});
}
}
using P = pair<int,int>;
vector<P> points;
for (auto query : queries) {
if (query.typ == Query<ll>::ADD) {
points.push_back({query.x, query.y});
}
}
SegTree2D<ll, SumSegTreeOp::op, SumSegTreeOp::e, int> st(points);
for (auto query : queries) {
if (query.typ == Query<ll>::ADD) {
P p{query.x, query.y};
st.set(p, st.get(p) + query.weight);
} else {
cout << st.prod(P{query.x, query.y}, P{query.x2, query.y2}) << '\n';
}
}
return 0;
}
#line 1 "DataStructure/test/segment_tree_2d_pointaddrectsum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_rectangle_sum"
#include <bits/stdc++.h>
using namespace std;
#line 1 "buffered_reader.h"
// Buffered reader {{{
namespace IO {
const int BUFSIZE = 1<<14;
char buf[BUFSIZE + 1], *inp = buf;
bool reacheof;
char get_char() {
if (!*inp && !reacheof) {
memset(buf, 0, sizeof buf);
int tmp = fread(buf, 1, BUFSIZE, stdin);
if (tmp != BUFSIZE) reacheof = true;
inp = buf;
}
return *inp++;
}
template<typename T>
T get() {
int neg = 0;
T res = 0;
char c = get_char();
while (!std::isdigit(c) && c != '-' && c != '+') c = get_char();
if (c == '+') { neg = 0; }
else if (c == '-') { neg = 1; }
else res = c - '0';
c = get_char();
while (std::isdigit(c)) {
res = res * 10 + (c - '0');
c = get_char();
}
return neg ? -res : res;
}
};
// Helper methods
int ri() {
return IO::get<int>();
}
// }}}
#line 1 "DataStructure/SegTree2D.h"
// 2D segment tree
#line 1 "DataStructure/SegTree.h"
// SegTree, copied from AtCoder library {{{
// AtCoder doc: https://atcoder.github.io/ac-library/master/document_en/segtree.html
//
// Notes:
// - Index of elements from 0 -> n-1
// - Range queries are [l, r-1]
//
// Tested:
// - (binary search) https://atcoder.jp/contests/practice2/tasks/practice2_j
// - https://oj.vnoi.info/problem/gss
// - https://oj.vnoi.info/problem/nklineup
// - (max_right & min_left for delete position queries) https://oj.vnoi.info/problem/segtree_itstr
// - https://judge.yosupo.jp/problem/point_add_range_sum
// - https://judge.yosupo.jp/problem/point_set_range_composite
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
template<
class T, // data type for nodes
T (*op) (T, T), // operator to combine 2 nodes
T (*e)() // identity element
>
struct SegTree {
SegTree() : SegTree(0) {}
explicit SegTree(int n) : SegTree(vector<T> (n, e())) {}
explicit SegTree(const vector<T>& v) : _n((int) v.size()) {
log = ceil_pow2(_n);
size = 1<<log;
d = vector<T> (2*size, e());
for (int i = 0; i < _n; i++) d[size+i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
// 0 <= p < n
void set(int p, T x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
// 0 <= p < n
T get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
// Get product in range [l, r-1]
// 0 <= l <= r <= n
// For empty segment (l == r) -> return e()
T prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
T sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
T all_prod() const {
return d[1];
}
// Binary search on SegTree to find largest r:
// f(op(a[l] .. a[r-1])) = true (assuming empty array is always true)
// f(op(a[l] .. a[r])) = false (assuming op(..., a[n]), which is out of bound, is always false)
template <bool (*f)(T)> int max_right(int l) const {
return max_right(l, [](T x) { return f(x); });
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
T sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
// Binary search on SegTree to find smallest l:
// f(op(a[l] .. a[r-1])) = true (assuming empty array is always true)
// f(op(a[l-1] .. a[r-1])) = false (assuming op(a[-1], ..), which is out of bound, is always false)
template <bool (*f)(T)> int min_left(int r) const {
return min_left(r, [](T x) { return f(x); });
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
T sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
vector<T> d;
void update(int k) {
d[k] = op(d[2*k], d[2*k+1]);
}
};
// }}}
// SegTree examples {{{
// Examples: Commonly used SegTree ops: max / min / sum
struct MaxSegTreeOp {
static int op(int x, int y) {
return max(x, y);
}
static int e() {
return INT_MIN;
}
};
struct MinSegTreeOp {
static int op(int x, int y) {
return min(x, y);
}
static int e() {
return INT_MAX;
}
};
struct SumSegTreeOp {
static long long op(long long x, long long y) {
return x + y;
}
static long long e() {
return 0;
}
};
// using STMax = SegTree<int, MaxSegTreeOp::op, MaxSegTreeOp::e>;
// using STMin = SegTree<int, MinSegTreeOp::op, MinSegTreeOp::e>;
// using STSum = SegTree<int, SumSegTreeOp::op, SumSegTreeOp::e>;
// }}}
#line 3 "DataStructure/SegTree2D.h"
template<
class S, // aggregate data type
S (*op) (S, S), // combine aggregate data
S (*e) (), // empty element
class Coord // for x and y coordinates
> struct SegTree2D {
using P = pair<Coord, Coord>;
// _points must contains all add queries
SegTree2D(const vector<P>& _points) : points(_points) {
sort(points.begin(), points.end());
points.erase(unique(points.begin(), points.end()), points.end());
n = points.size();
// init segtrees
coords.resize(n * 2);
for (int i = 0; i < n; i++) {
coords[n + i] = {{points[i].second, points[i].first}};
}
for (int i = n-1; i > 0; i--) {
std::merge(coords[i*2].begin(), coords[i*2].end(),
coords[i*2+1].begin(), coords[i*2+1].end(),
std::back_inserter(coords[i]));
coords[i].erase(unique(coords[i].begin(), coords[i].end()), coords[i].end());
}
for (const auto& c : coords) {
segs.emplace_back(SegTree<S, op, e>(c.size()));
}
}
// Set value(p) = val
void set(P p, S val) {
int i = lower_bound(points.begin(), points.end(), p) - points.begin();
assert(i < n && points[i] == p);
for (i += n; i; i >>= 1) {
int j = lower_bound(coords[i].begin(), coords[i].end(), P{p.second, p.first}) - coords[i].begin();
segs[i].set(j, val);
}
}
// Get value at p
S get(P p) const {
return prod(p, P{p.first + 1, p.second + 1});
}
// Get sum of points in rectangles, given bottom-left and top-right
// [low.x, high.x - 1] * [low.y, high.y - 1]
S prod(P low, P high) const {
assert(low.first <= high.first);
assert(low.second <= high.second);
if (low.first == high.first) return e();
if (low.second == high.second) return e();
int l = n + (lower_bound(points.begin(), points.end(), low, cmpFirst) - points.begin());
int r = n + (lower_bound(points.begin(), points.end(), high, cmpFirst) - points.begin());
S res = e();
while (l < r) {
if (l & 1) res = op(res, prod_1d(l++, low.second, high.second));
if (r & 1) res = op(res, prod_1d(--r, low.second, high.second));
l >>= 1; r >>= 1;
}
return res;
}
// private:
S prod_1d(int x, Coord l, Coord r) const {
auto il = lower_bound(coords[x].begin(), coords[x].end(), P{l, l}, cmpFirst) - coords[x].begin();
auto ir = lower_bound(coords[x].begin(), coords[x].end(), P{r, r}, cmpFirst) - coords[x].begin();
return segs[x].prod(il, ir);
}
static bool cmpFirst(const P& u, const P& v) {
return u.first < v.first;
}
int n;
vector<P> points;
// segtrees, outer layer by x-coordinate
vector<vector<P>> coords; // coords[i] stores all points maintained by i-th node in ST
vector<SegTree<S, op, e>> segs;
};
#line 8 "DataStructure/test/segment_tree_2d_pointaddrectsum.test.cpp"
#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)
template<typename T>
struct Query {
static const int ADD = 0;
static const int QUERY = 1;
int typ; // ADD or QUERY
int x, y;
int x2, y2; // for QUERY: [x1, x2-1] * [y1, y2-1]
T weight;
};
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n = IO::get<int>();
int q = IO::get<int>();
using ll = long long;
vector<Query<ll>> queries;
REP(i,n) {
int x = IO::get<int>();
int y = IO::get<int>();
ll val = IO::get<ll>();
queries.push_back({Query<ll>::ADD, x, y, -1, -1, val});
}
REP(i,q) {
int typ = IO::get<int>();
if (typ == 0) {
int x = IO::get<int>();
int y = IO::get<int>();
ll val = IO::get<ll>();
queries.push_back({Query<ll>::ADD, x, y, -1, -1, val});
} else {
int x = IO::get<int>();
int y = IO::get<int>();
int x2 = IO::get<int>();
int y2 = IO::get<int>();
queries.push_back({Query<ll>::QUERY, x, y, x2, y2, 0});
}
}
using P = pair<int,int>;
vector<P> points;
for (auto query : queries) {
if (query.typ == Query<ll>::ADD) {
points.push_back({query.x, query.y});
}
}
SegTree2D<ll, SumSegTreeOp::op, SumSegTreeOp::e, int> st(points);
for (auto query : queries) {
if (query.typ == Query<ll>::ADD) {
P p{query.x, query.y};
st.set(p, st.get(p) + query.weight);
} else {
cout << st.prod(P{query.x, query.y}, P{query.x2, query.y2}) << '\n';
}
}
return 0;
}