This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"
// header file section
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
#include "../../segment_tree/persistent_segment_tree.hpp"
#include "../../util/coordinate_compression.hpp"
using namespace std;
using llong = long long;
struct Monoid {
using value_type = llong;
static llong operation(llong a, llong b) {
return a + b;
};
static llong identity() {
return 0;
}
};
llong n, q;
vector<PersistentSegmentTree<Monoid>> v;
vector<tuple<llong, llong, llong>> p;
CoordinateCompressionBuilder<llong> x_axis_builder;
CoordinateCompressionBuilder<llong> y_axis_builder;
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> n >> q;
for (int i = 0; i < n; i++) {
llong x, y, w;
cin >> x >> y >> w;
p.push_back(tie(y, x, w));
x_axis_builder.push(x);
y_axis_builder.push(y);
}
sort(p.begin(), p.end());
auto x_axis = x_axis_builder.build();
auto y_axis = y_axis_builder.build();
v.push_back(PersistentSegmentTree<Monoid>(x_axis.size()));
for (int i = 0; i < p.size(); i++) {
llong x, y, w;
tie(y, x, w) = p[i];
x = x_axis.zip(x);
y = y_axis.zip(y);
if (v.size() <= y) {
v.push_back(v[y - 1]);
}
v[y] = v[y].update(x, v[y][x] + w);
}
for (int i = 0; i < q; i++) {
llong l, d, r, u;
cin >> l >> d >> r >> u;
l = x_axis.zip(l);
r = x_axis.zip(r);
d = y_axis.zip(d) - 1;
u = y_axis.zip(u) - 1;
if (d >= 0)
cout << v[u].fold(l, r) - v[d].fold(l, r) << '\n';
else if (u >= 0)
cout << v[u].fold(l, r) << '\n';
else
cout << 0 << '\n';
}
return 0;
};
#line 1 "test/yosupo/rectangle_sum1.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_sum"
// header file section
#include <algorithm>
#include <bitset>
#include <cfloat>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
#line 1 "segment_tree/persistent_segment_tree.hpp"
#include <cstddef>
#include <cstdint>
#line 7 "segment_tree/persistent_segment_tree.hpp"
#include <iterator>
#line 9 "segment_tree/persistent_segment_tree.hpp"
template <class Monoid>
struct PersistentSegmentTree {
using uint = size_t;
using T = typename Monoid::value_type;
struct Node {
T dat;
Node *l = nullptr, *r = nullptr;
Node(T dat) : dat(dat){};
};
Node *root;
uint n;
Node *merge_node(Node *lch, Node *rch) {
T l = (lch ? lch->dat : Monoid::identity());
T r = (rch ? rch->dat : Monoid::identity());
Node *ret = new Node(Monoid::operation(l, r));
ret->l = lch;
ret->r = rch;
return ret;
};
PersistentSegmentTree(const PersistentSegmentTree &) = default;
PersistentSegmentTree &operator=(const PersistentSegmentTree &) = default;
PersistentSegmentTree(uint n, Node *r) : root(r), n(n){};
PersistentSegmentTree(uint n)
: root(alloc(0, n, std::vector<T>(n, Monoid::identity()))), n(n){};
template <class InputItr>
PersistentSegmentTree(const InputItr first, const InputItr last)
: n(std::distance(first, last)),
root(alloc(0, n, std::vector<T>(first, last))){};
Node *alloc(uint nl, uint nr, const std::vector<T> &v) {
if (nr - nl <= 1)
return new Node(v[nl]);
else
return merge_node(alloc(nl, (nl + nr) / 2, v),
alloc((nl + nr) / 2, nr, v));
};
const T fold(uint l, uint r) const {
return fold(l, r, 0, n, root);
};
const T fold(uint ql, uint qr, uint nl, uint nr, const Node *np) const {
if (np == nullptr || qr <= nl || nr <= ql)
return Monoid::identity();
else if (ql <= nl && nr <= qr)
return np->dat;
else
return Monoid::operation(fold(ql, qr, nl, (nl + nr) / 2, np->l),
fold(ql, qr, (nl + nr) / 2, nr, np->r));
};
PersistentSegmentTree update(uint idx, T d) {
return set(idx, d);
};
PersistentSegmentTree set(uint idx, T d) {
return PersistentSegmentTree(n, update(0, n, idx, d, root));
};
Node *update(uint nl, uint nr, uint idx, T d, Node *np) {
if (idx < nl || nr <= idx)
return np;
else if (nr - nl == 1)
return new Node(d);
else
return merge_node(update(nl, (nl + nr) / 2, idx, d, np->l),
update((nl + nr) / 2, nr, idx, d, np->r));
};
PersistentSegmentTree get_tree() {
return *this;
};
T operator[](uint idx) {
return fold(idx, idx + 1, 0, n, root);
};
};
#line 1 "util/coordinate_compression.hpp"
#line 5 "util/coordinate_compression.hpp"
template <class T>
struct CoordinateCompression {
std::vector<T> p;
template <class InputItr>
CoordinateCompression(InputItr first, InputItr last) : p(first, last) {
std::sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
};
int zip(T x) {
return std::lower_bound(p.begin(), p.end(), x) - p.begin();
};
T unzip(int x) {
return p[x];
};
int size() {
return p.size();
};
};
template <class T>
struct CoordinateCompressionBuilder {
std::vector<T> p;
CoordinateCompressionBuilder() = default;
template <class InputItr>
CoordinateCompressionBuilder(InputItr first, InputItr last)
: p(first, last){};
void push(T x) {
p.push_back(x);
};
CoordinateCompression<T> build() {
return CoordinateCompression<T>(p.begin(), p.end());
};
};
#line 19 "test/yosupo/rectangle_sum1.test.cpp"
using namespace std;
using llong = long long;
struct Monoid {
using value_type = llong;
static llong operation(llong a, llong b) {
return a + b;
};
static llong identity() {
return 0;
}
};
llong n, q;
vector<PersistentSegmentTree<Monoid>> v;
vector<tuple<llong, llong, llong>> p;
CoordinateCompressionBuilder<llong> x_axis_builder;
CoordinateCompressionBuilder<llong> y_axis_builder;
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin >> n >> q;
for (int i = 0; i < n; i++) {
llong x, y, w;
cin >> x >> y >> w;
p.push_back(tie(y, x, w));
x_axis_builder.push(x);
y_axis_builder.push(y);
}
sort(p.begin(), p.end());
auto x_axis = x_axis_builder.build();
auto y_axis = y_axis_builder.build();
v.push_back(PersistentSegmentTree<Monoid>(x_axis.size()));
for (int i = 0; i < p.size(); i++) {
llong x, y, w;
tie(y, x, w) = p[i];
x = x_axis.zip(x);
y = y_axis.zip(y);
if (v.size() <= y) {
v.push_back(v[y - 1]);
}
v[y] = v[y].update(x, v[y][x] + w);
}
for (int i = 0; i < q; i++) {
llong l, d, r, u;
cin >> l >> d >> r >> u;
l = x_axis.zip(l);
r = x_axis.zip(r);
d = y_axis.zip(d) - 1;
u = y_axis.zip(u) - 1;
if (d >= 0)
cout << v[u].fold(l, r) - v[d].fold(l, r) << '\n';
else if (u >= 0)
cout << v[u].fold(l, r) << '\n';
else
cout << 0 << '\n';
}
return 0;
};