This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_add_point_get"
#include <bits/stdc++.h>
using namespace std;
#include "../../../lib/data_structure/range_tree.hpp"
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n >> q;
vector<int> l(n), d(n), r(n), u(n);
vector<long long> w(n);
RangeTree<int, long long> rt;
for(int i = 0; i < n; i++){
cin >> l[i] >> d[i] >> r[i] >> u[i] >> w[i];
rt.add_point(l[i], d[i]);
rt.add_point(l[i], u[i]);
rt.add_point(r[i], d[i]);
rt.add_point(r[i], u[i]);
}
using T = tuple<int, int, int, int, int, long long>;
vector<T> query(q);
for(int i = 0; i < q; i++){
int T; cin >> T;
if(T == 0){
int L, D, R, U;
long long W;
cin >> L >> D >> R >> U >> W;
rt.add_point(L, D);
rt.add_point(L, U);
rt.add_point(R, D);
rt.add_point(R, U);
query[i] = {T, L, D, R, U, W};
}else{
int X, Y; cin >> X >> Y;
query[i] = {T, X, Y, 0, 0, 0};
}
}
rt.build();
for(int i = 0; i < n; i++){
rt.add(l[i], d[i], w[i]);
rt.add(l[i], u[i], -w[i]);
rt.add(r[i], d[i], -w[i]);
rt.add(r[i], u[i], w[i]);
}
for(int i = 0; i < q; i++){
auto [T, A, B, C, D, E] = query[i];
if(T == 0){
rt.add(A, B, E);
rt.add(A, D, -E);
rt.add(C, B, -E);
rt.add(C, D, E);
}else{
cout << rt.sum(A + 1, B + 1) << "\n";
}
}
}
#line 1 "test/library_checker/data_structure/rectangle_add_point_get.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_add_point_get"
#include <bits/stdc++.h>
using namespace std;
#line 2 "lib/data_structure/range_tree.hpp"
template <typename S, typename T>
struct RangeTree{
struct BinaryIndexedTree{
int N;
vector<T> BIT;
BinaryIndexedTree() {}
void init(int size){
N = size;
BIT.assign(N + 1, 0);
}
T get(int i){
return sum(i + 1) - sum(i);
}
void add(int i, T x){
++i;
while(i <= N){
BIT[i] += x;
i += i & -i;
}
}
T sum(int i) const {
T ans = 0;
while(i > 0){
ans += BIT[i];
i -= i & -i;
}
return ans;
}
T sum(int L, int R) const {
return sum(R) - sum(L);
}
};
using P = pair<S, S>;
S N, M;
vector<BinaryIndexedTree> bit;
vector<vector<S>> ys;
vector<P> ps;
RangeTree() {}
void add_point(S x, S y){
ps.push_back(make_pair(x, y));
}
void build(){
sort(ps.begin(), ps.end());
ps.erase(unique(ps.begin(), ps.end()), ps.end());
N = ps.size();
bit.resize(N + 1);
ys.resize(N + 1);
for(int i = 0; i <= N; ++i){
int j = i + 1;
while(j <= N){
ys[j].push_back(ps[i].second);
j += j & -j;
}
sort(ys[i].begin(), ys[i].end());
ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
bit[i].init(ys[i].size());
}
}
int id(S x) const {
auto f = [](const P &a, const P &b){
return a.first < b.first;
};
return lower_bound(ps.begin(), ps.end(), make_pair(x, S()), f) - ps.begin();
}
int id(int i, S y) const {
return lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin();
}
void add(S x, S y, T a){
int i = lower_bound(ps.begin(), ps.end(), make_pair(x, y)) - ps.begin();
assert(ps[i] == make_pair(x, y));
++i;
while(i <= N){
bit[i].add(id(i, y), a);
i += i & -i;
}
}
T sum(S x, S y) const {
T ret = T();
int a = id(x);
while(a > 0){
ret += bit[a].sum(id(a, y));
a -= a & -a;
}
return ret;
}
// [(xl, yl), (xr, yr))
T sum(S xl, S yl, S xr, S yr) const {
T ret = T();
int a = id(xl), b = id(xr);
while(a != b) {
if(a < b){
ret += bit[b].sum(id(b, yl), id(b, yr));
b -= b & -b;
} else{
ret -= bit[a].sum(id(a, yl), id(a, yr));
a -= a & -a;
}
}
return ret;
}
};
#line 6 "test/library_checker/data_structure/rectangle_add_point_get.test.cpp"
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n >> q;
vector<int> l(n), d(n), r(n), u(n);
vector<long long> w(n);
RangeTree<int, long long> rt;
for(int i = 0; i < n; i++){
cin >> l[i] >> d[i] >> r[i] >> u[i] >> w[i];
rt.add_point(l[i], d[i]);
rt.add_point(l[i], u[i]);
rt.add_point(r[i], d[i]);
rt.add_point(r[i], u[i]);
}
using T = tuple<int, int, int, int, int, long long>;
vector<T> query(q);
for(int i = 0; i < q; i++){
int T; cin >> T;
if(T == 0){
int L, D, R, U;
long long W;
cin >> L >> D >> R >> U >> W;
rt.add_point(L, D);
rt.add_point(L, U);
rt.add_point(R, D);
rt.add_point(R, U);
query[i] = {T, L, D, R, U, W};
}else{
int X, Y; cin >> X >> Y;
query[i] = {T, X, Y, 0, 0, 0};
}
}
rt.build();
for(int i = 0; i < n; i++){
rt.add(l[i], d[i], w[i]);
rt.add(l[i], u[i], -w[i]);
rt.add(r[i], d[i], -w[i]);
rt.add(r[i], u[i], w[i]);
}
for(int i = 0; i < q; i++){
auto [T, A, B, C, D, E] = query[i];
if(T == 0){
rt.add(A, B, E);
rt.add(A, D, -E);
rt.add(C, B, -E);
rt.add(C, D, E);
}else{
cout << rt.sum(A + 1, B + 1) << "\n";
}
}
}