firiexp's Library
This documentation is automatically generated by online-judge-tools/verification-helper
test/yosupo_rectangle_add_point_get.test.cpp
- View this file on GitHub
- Last update: 2026-03-22 13:47:31+09:00
- Problem: https://judge.yosupo.jp/problem/rectangle_add_point_get
Depends on
- 長方形加算点取得(Rectangle Add Point Get)
(datastructure/rectangle_add_point_get.cpp)
- 高速入出力(Fast IO)
(util/fastio.cpp)
Code
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_add_point_get"
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <string>
#include <type_traits>
#include "../util/fastio.cpp"
#include "../datastructure/rectangle_add_point_get.cpp"
int main() {
Scanner sc;
Printer pr;
int n, q;
sc.read(n, q);
RectangleAddPointGet<long long> solver;
for (int i = 0; i < n; ++i) {
int l, d, r, u;
long long w;
sc.read(l, d, r, u, w);
solver.add_rectangle(l, d, r, u, w);
}
for (int i = 0; i < q; ++i) {
int t;
sc.read(t);
if (t == 0) {
int l, d, r, u;
long long w;
sc.read(l, d, r, u, w);
solver.add_rectangle(l, d, r, u, w);
} else {
int x, y;
sc.read(x, y);
solver.add_query(x, y);
}
}
auto ans = solver.solve();
for (auto &&x : ans) pr.println(x);
return 0;
}#line 1 "test/yosupo_rectangle_add_point_get.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/rectangle_add_point_get"
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <string>
#include <type_traits>
#line 1 "util/fastio.cpp"
using namespace std;
extern "C" int fileno(FILE *);
extern "C" int isatty(int);
template<class T, class = void>
struct is_fastio_range : false_type {};
template<class T>
struct is_fastio_range<T, void_t<decltype(declval<T &>().begin()), decltype(declval<T &>().end())>> : true_type {};
template<class T, class = void>
struct has_fastio_value : false_type {};
template<class T>
struct has_fastio_value<T, void_t<decltype(declval<const T &>().value())>> : true_type {};
struct FastIoDigitTable {
char num[40000];
constexpr FastIoDigitTable() : num() {
for (int i = 0; i < 10000; ++i) {
int x = i;
for (int j = 3; j >= 0; --j) {
num[i * 4 + j] = char('0' + x % 10);
x /= 10;
}
}
}
};
struct Scanner {
static constexpr int BUFSIZE = 1 << 17;
static constexpr int OFFSET = 64;
char buf[BUFSIZE + 1];
int idx, size;
bool interactive;
Scanner() : idx(0), size(0), interactive(isatty(fileno(stdin))) {}
inline void load() {
int len = size - idx;
memmove(buf, buf + idx, len);
if (interactive) {
if (fgets(buf + len, BUFSIZE + 1 - len, stdin)) size = len + (int)strlen(buf + len);
else size = len;
} else {
size = len + (int)fread(buf + len, 1, BUFSIZE - len, stdin);
}
idx = 0;
buf[size] = 0;
}
inline void ensure() {
if (idx + OFFSET > size) load();
}
inline void ensure_interactive() {
if (idx == size) load();
}
inline char skip() {
if (interactive) {
ensure_interactive();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure_interactive();
}
return buf[idx++];
}
ensure();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure();
}
return buf[idx++];
}
template<class T, typename enable_if<is_integral<T>::value, int>::type = 0>
void read(T &x) {
if (interactive) {
char c = skip();
bool neg = false;
if constexpr (is_signed<T>::value) {
if (c == '-') {
neg = true;
ensure_interactive();
c = buf[idx++];
}
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
ensure_interactive();
c = buf[idx++];
}
if constexpr (is_signed<T>::value) {
if (neg) x = -x;
}
return;
}
char c = skip();
bool neg = false;
if constexpr (is_signed<T>::value) {
if (c == '-') {
neg = true;
c = buf[idx++];
}
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
c = buf[idx++];
}
if constexpr (is_signed<T>::value) {
if (neg) x = -x;
}
}
template<class T, typename enable_if<!is_integral<T>::value && !is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value && has_fastio_value<T>::value, int>::type = 0>
void read(T &x) {
long long v;
read(v);
x = T(v);
}
template<class Head, class Next, class... Tail>
void read(Head &head, Next &next, Tail &...tail) {
read(head);
read(next, tail...);
}
template<class T, class U>
void read(pair<T, U> &p) {
read(p.first, p.second);
}
template<class T, typename enable_if<is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value, int>::type = 0>
void read(T &a) {
for (auto &x : a) read(x);
}
void read(char &c) {
c = skip();
}
void read(string &s) {
s.clear();
if (interactive) {
ensure_interactive();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure_interactive();
}
while (true) {
int start = idx;
while (idx < size && buf[idx] > ' ') ++idx;
s.append(buf + start, idx - start);
if (idx < size) break;
load();
if (size == 0) break;
}
if (idx < size) ++idx;
return;
}
ensure();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure();
}
while (true) {
int start = idx;
while (idx < size && buf[idx] > ' ') ++idx;
s.append(buf + start, idx - start);
if (idx < size) break;
load();
}
if (idx < size) ++idx;
}
};
struct Printer {
static constexpr int BUFSIZE = 1 << 17;
static constexpr int OFFSET = 64;
char buf[BUFSIZE];
int idx;
bool interactive;
inline static constexpr FastIoDigitTable table{};
Printer() : idx(0), interactive(isatty(fileno(stdout))) {}
~Printer() { flush(); }
inline void flush() {
if (idx) {
fwrite(buf, 1, idx, stdout);
idx = 0;
}
}
inline void pc(char c) {
if (idx > BUFSIZE - OFFSET) flush();
buf[idx++] = c;
if (interactive && c == '\n') flush();
}
inline void print_range(const char *s, size_t n) {
size_t pos = 0;
while (pos < n) {
if (idx == BUFSIZE) flush();
size_t chunk = min(n - pos, (size_t)(BUFSIZE - idx));
memcpy(buf + idx, s + pos, chunk);
idx += (int)chunk;
pos += chunk;
}
}
void print(const char *s) {
print_range(s, strlen(s));
}
void print(const string &s) {
print_range(s.data(), s.size());
}
void print(char c) {
pc(c);
}
void print(bool b) {
pc(char('0' + (b ? 1 : 0)));
}
template<class T, typename enable_if<is_integral<T>::value && !is_same<T, bool>::value, int>::type = 0>
void print(T x) {
if (idx > BUFSIZE - 100) flush();
using U = typename make_unsigned<T>::type;
U y;
if constexpr (is_signed<T>::value) {
if (x < 0) {
buf[idx++] = '-';
y = U(0) - static_cast<U>(x);
} else {
y = static_cast<U>(x);
}
} else {
y = x;
}
if (y == 0) {
buf[idx++] = '0';
return;
}
static constexpr int TMP_SIZE = sizeof(U) * 10 / 4;
char tmp[TMP_SIZE];
int pos = TMP_SIZE;
while (y >= 10000) {
pos -= 4;
memcpy(tmp + pos, table.num + (y % 10000) * 4, 4);
y /= 10000;
}
if (y >= 1000) {
memcpy(buf + idx, table.num + (y << 2), 4);
idx += 4;
} else if (y >= 100) {
memcpy(buf + idx, table.num + (y << 2) + 1, 3);
idx += 3;
} else if (y >= 10) {
unsigned q = (unsigned(y) * 205) >> 11;
buf[idx] = char('0' + q);
buf[idx + 1] = char('0' + (unsigned(y) - q * 10));
idx += 2;
} else {
buf[idx++] = char('0' + y);
}
memcpy(buf + idx, tmp + pos, TMP_SIZE - pos);
idx += TMP_SIZE - pos;
}
template<class T, typename enable_if<!is_integral<T>::value && !is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value && has_fastio_value<T>::value, int>::type = 0>
void print(const T &x) {
print(x.value());
}
template<class T, typename enable_if<is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value, int>::type = 0>
void print(const T &a) {
bool first = true;
for (auto &&x : a) {
if (!first) pc(' ');
first = false;
print(x);
}
}
template<class T>
void println(const T &x) {
print(x);
pc('\n');
}
template<class Head, class... Tail>
void println(const Head &head, const Tail &...tail) {
print(head);
((pc(' '), print(tail)), ...);
pc('\n');
}
void println() {
pc('\n');
}
};
template<class T>
Scanner &operator>>(Scanner &in, T &x) {
in.read(x);
return in;
}
template<class T>
Printer &operator<<(Printer &out, const T &x) {
out.print(x);
return out;
}
/**
* @brief 高速入出力(Fast IO)
*/
#line 1 "datastructure/rectangle_add_point_get.cpp"
using namespace std;
template<class T>
struct RectangleAddPointGet {
struct Operation {
int type;
int l, d, r, u;
T w;
};
vector<Operation> ops;
vector<int> xs;
void add_rectangle(int l, int d, int r, int u, T w) {
ops.push_back({0, l, d, r, u, w});
xs.push_back(l);
xs.push_back(r);
}
void add_query(int x, int y) {
ops.push_back({1, x, y, 0, 0, 0});
}
vector<T> solve() const {
struct RectInfo {
int start[4];
};
vector<int> ord_x = xs;
ord_x.reserve(ord_x.size() + ops.size());
for (auto &&op : ops) {
if (op.type == 1) ord_x.push_back(op.l);
}
sort(ord_x.begin(), ord_x.end());
ord_x.erase(unique(ord_x.begin(), ord_x.end()), ord_x.end());
int m = (int)ord_x.size();
vector<int> x_index_lower(ops.size());
vector<int> x_index_upper(ops.size());
for (int idx = 0; idx < (int)ops.size(); ++idx) {
x_index_lower[idx] = (int)(lower_bound(ord_x.begin(), ord_x.end(), ops[idx].l) - ord_x.begin()) + 1;
if (ops[idx].type == 1) {
x_index_upper[idx] = (int)(upper_bound(ord_x.begin(), ord_x.end(), ops[idx].l) - ord_x.begin());
} else {
x_index_upper[idx] = (int)(lower_bound(ord_x.begin(), ord_x.end(), ops[idx].r) - ord_x.begin()) + 1;
}
}
vector<int> cnt(m + 1);
auto count_point = [&](int xi) {
for (int i = xi; i <= m; i += i & -i) ++cnt[i];
};
for (int idx = 0; idx < (int)ops.size(); ++idx) {
if (ops[idx].type == 1) continue;
count_point(x_index_lower[idx]);
count_point(x_index_lower[idx]);
count_point(x_index_upper[idx]);
count_point(x_index_upper[idx]);
}
vector<vector<int>> ys(m + 1);
for (int i = 1; i <= m; ++i) ys[i].reserve(cnt[i]);
auto reserve_point = [&](int xi, int y) {
for (int i = xi; i <= m; i += i & -i) ys[i].push_back(y);
};
for (int idx = 0; idx < (int)ops.size(); ++idx) {
auto &&op = ops[idx];
if (op.type == 0) {
reserve_point(x_index_lower[idx], op.d);
reserve_point(x_index_lower[idx], op.u);
reserve_point(x_index_upper[idx], op.d);
reserve_point(x_index_upper[idx], op.u);
}
}
for (int i = 1; i <= m; ++i) {
sort(ys[i].begin(), ys[i].end());
ys[i].erase(unique(ys[i].begin(), ys[i].end()), ys[i].end());
}
vector<int> offset(m + 2, 0);
for (int i = 1; i <= m; ++i) offset[i + 1] = offset[i] + (int)ys[i].size();
vector<T> bit(offset[m + 1], 0);
auto path_len_add = [&](int xi) {
int len = 0;
for (int i = xi; i <= m; i += i & -i) ++len;
return len;
};
auto path_len_sum = [&](int xi) {
int len = 0;
for (int i = xi; i > 0; i -= i & -i) ++len;
return len;
};
vector<RectInfo> rect_info(ops.size());
vector<int> query_start(ops.size(), -1);
int total_add_visits = 0, total_sum_visits = 0;
for (int idx = 0; idx < (int)ops.size(); ++idx) {
if (ops[idx].type == 0) {
total_add_visits += path_len_add(x_index_lower[idx]) * 2;
total_add_visits += path_len_add(x_index_upper[idx]) * 2;
} else {
total_sum_visits += path_len_sum(x_index_upper[idx]);
}
}
vector<int> add_yi(total_add_visits);
vector<int> sum_yi(total_sum_visits);
int add_ptr = 0, sum_ptr = 0;
auto encode_add = [&](int xi, int y) {
int start = add_ptr;
for (int i = xi; i <= m; i += i & -i) {
add_yi[add_ptr++] = (int)(lower_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin()) + 1;
}
return start;
};
auto encode_sum = [&](int xi, int y) {
int start = sum_ptr;
for (int i = xi; i > 0; i -= i & -i) {
sum_yi[sum_ptr++] = (int)(upper_bound(ys[i].begin(), ys[i].end(), y) - ys[i].begin());
}
return start;
};
for (int idx = 0; idx < (int)ops.size(); ++idx) {
auto &&op = ops[idx];
if (op.type == 0) {
rect_info[idx].start[0] = encode_add(x_index_lower[idx], op.d);
rect_info[idx].start[1] = encode_add(x_index_lower[idx], op.u);
rect_info[idx].start[2] = encode_add(x_index_upper[idx], op.d);
rect_info[idx].start[3] = encode_add(x_index_upper[idx], op.u);
} else {
query_start[idx] = encode_sum(x_index_upper[idx], op.d);
}
}
auto add_point = [&](int xi, int start, T w) {
int ptr = start;
for (int i = xi; i <= m; i += i & -i) {
int yi = add_yi[ptr++];
int sz = (int)ys[i].size();
int base = offset[i];
for (; yi <= sz; yi += yi & -yi) bit[base + yi - 1] += w;
}
};
auto prefix_sum = [&](int xi, int start) {
T ret = 0;
int ptr = start;
for (int i = xi; i > 0; i -= i & -i) {
int yi = sum_yi[ptr++];
int base = offset[i];
for (; yi > 0; yi -= yi & -yi) ret += bit[base + yi - 1];
}
return ret;
};
vector<T> ans;
for (int idx = 0; idx < (int)ops.size(); ++idx) {
auto &&op = ops[idx];
if (op.type == 0) {
add_point(x_index_lower[idx], rect_info[idx].start[0], op.w);
add_point(x_index_lower[idx], rect_info[idx].start[1], -op.w);
add_point(x_index_upper[idx], rect_info[idx].start[2], -op.w);
add_point(x_index_upper[idx], rect_info[idx].start[3], op.w);
} else {
ans.push_back(prefix_sum(x_index_upper[idx], query_start[idx]));
}
}
return ans;
}
};
/**
* @brief 長方形加算点取得(Rectangle Add Point Get)
*/
#line 13 "test/yosupo_rectangle_add_point_get.test.cpp"
int main() {
Scanner sc;
Printer pr;
int n, q;
sc.read(n, q);
RectangleAddPointGet<long long> solver;
for (int i = 0; i < n; ++i) {
int l, d, r, u;
long long w;
sc.read(l, d, r, u, w);
solver.add_rectangle(l, d, r, u, w);
}
for (int i = 0; i < q; ++i) {
int t;
sc.read(t);
if (t == 0) {
int l, d, r, u;
long long w;
sc.read(l, d, r, u, w);
solver.add_rectangle(l, d, r, u, w);
} else {
int x, y;
sc.read(x, y);
solver.add_query(x, y);
}
}
auto ans = solver.solve();
for (auto &&x : ans) pr.println(x);
return 0;
}