cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
test/src/datastructure/fenwick_tree/static_rectangle_add_rectangle_sum/dummy.test.cpp
- View this file on GitHub
- Last update: 2023-07-09 04:04:16+09:00
- Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A
Depends on
- Fenwick Tree
(library/datastructure/fenwick_tree/fenwick_tree.hpp)
- Static Rectangle Add Rectangle Sum
(library/datastructure/fenwick_tree/static_rectangle_add_rectangle_sum.hpp)
- Tuple Ops
(library/util/tuple_ops.hpp)
Code
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <iostream>
#include <random>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
#include "library/datastructure/fenwick_tree/static_rectangle_add_rectangle_sum.hpp"
using namespace suisen;
template <typename T, int H, int W>
std::vector<T> static_rectangle_add_rectangle_sum_naive(const std::vector<AddQuery<T>>& add_queries, const std::vector<SumQuery>& sum_queries) {
std::array<std::array<T, H>, W> dat;
for (auto& row : dat) row.fill(T{ 0 });
for (const auto& q : add_queries) {
for (int x = q.l; x < q.r; ++x) for (int y = q.d; y < q.u; ++y) {
dat[x][y] += q.val;
}
}
std::vector<T> res(sum_queries.size(), T{ 0 });
for (std::size_t query_id = 0; query_id < sum_queries.size(); ++query_id) {
const auto& q = sum_queries[query_id];
mint& ans = res[query_id];
for (int x = q.l; x < q.r; ++x) for (int y = q.d; y < q.u; ++y) {
ans += dat[x][y];
}
}
return res;
}
template <int H, int W, int AddQ, int SumQ>
void random_test(uint32_t seed = ~uint32_t(0)) {
std::mt19937 rng{ seed != ~uint32_t(0) ? seed : std::random_device{}() };
std::vector<AddQuery<mint>> add_queries(AddQ);
std::vector<SumQuery> sum_queries(SumQ);
std::uniform_int_distribution<int> dist_x(0, H - 1), dist_y(0, W - 1), dist_val(0, mint::mod() - 1);
for (int i = 0; i < AddQ; ++i) {
int l = dist_x(rng), r = dist_x(rng);
if (l > r) std::swap(l, r);
int d = dist_y(rng), u = dist_y(rng);
if (d > u) std::swap(d, u);
int val = dist_val(rng);
add_queries[i] = { l, r, d, u, val };
}
for (int i = 0; i < SumQ; ++i) {
int l = dist_x(rng), r = dist_x(rng);
if (l > r) std::swap(l, r);
int d = dist_y(rng), u = dist_y(rng);
if (d > u) std::swap(d, u);
sum_queries[i] = { l, r, d, u };
}
auto actual = static_rectangle_add_rectangle_sum(add_queries, sum_queries);
auto expected = static_rectangle_add_rectangle_sum_naive<mint, H, W>(add_queries, sum_queries);
assert(actual == expected);
}
int main() {
random_test<1000, 1000, 1000, 1000>();
std::cout << "Hello World" << std::endl;
return 0;
}#line 1 "test/src/datastructure/fenwick_tree/static_rectangle_add_rectangle_sum/dummy.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <iostream>
#include <random>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
#line 1 "library/datastructure/fenwick_tree/static_rectangle_add_rectangle_sum.hpp"
#include <algorithm>
#line 1 "library/util/tuple_ops.hpp"
#include <tuple>
namespace suisen {
namespace internal::tuple_ops {
template <std::size_t N, typename F, typename ...Args>
std::tuple<Args...>& update(std::tuple<Args...> &lhs, F &&fun) {
if constexpr (N == std::tuple_size_v<std::tuple<Args...>>) return lhs;
else return fun(std::get<N>(lhs)), update<N + 1>(lhs, std::forward<F>(fun));
}
template <std::size_t N, typename F, typename ...Args>
std::tuple<Args...>& merge(std::tuple<Args...> &lhs, const std::tuple<Args...>& rhs, F &&fun) {
if constexpr (N == std::tuple_size_v<std::tuple<Args...>>) return lhs;
else return fun(std::get<N>(lhs), std::get<N>(rhs)), merge<N + 1>(lhs, rhs, std::forward<F>(fun));
}
}
template <typename ...Args>
std::tuple<Args...>& operator+=(std::tuple<Args...>& t1, const std::tuple<Args...>& t2) {
return internal::tuple_ops::merge<0>(t1, t2, [](auto &x, const auto &y) { x += y; });
}
template <typename ...Args>
std::tuple<Args...>& operator-=(std::tuple<Args...>& t1, const std::tuple<Args...>& t2) {
return internal::tuple_ops::merge<0>(t1, t2, [](auto &x, const auto &y) { x -= y; });
}
template <typename ...Args>
std::tuple<Args...> operator+(std::tuple<Args...> t1, const std::tuple<Args...>& t2) { return std::move(t1 += t2); }
template <typename ...Args>
std::tuple<Args...> operator-(std::tuple<Args...> t1, const std::tuple<Args...>& t2) { return std::move(t1 -= t2); }
template <typename V, typename ...Args>
std::tuple<Args...>& operator*=(std::tuple<Args...>& t1, const V &v) { return internal::tuple_ops::update<0>(t1, [&v](auto &x) { x *= v; }); }
template <typename V, typename ...Args>
std::tuple<Args...>& operator/=(std::tuple<Args...>& t1, const V &v) { return internal::tuple_ops::update<0>(t1, [&v](auto &x) { x /= v; }); }
template <typename V, typename ...Args>
std::tuple<Args...> operator*(const V &v, std::tuple<Args...> t1) { return std::move(t1 *= v); }
template <typename V, typename ...Args>
std::tuple<Args...> operator*(std::tuple<Args...> t1, const V &v) { return std::move(t1 *= v); }
template <typename V, typename ...Args>
std::tuple<Args...> operator/(std::tuple<Args...> t1, const V &v) { return std::move(t1 /= v); }
} // namespace suisen
#line 1 "library/datastructure/fenwick_tree/fenwick_tree.hpp"
#include <vector>
#include <map>
#include <unordered_map>
namespace suisen {
namespace internal {
template <typename T, typename index_t = int, typename Container = std::vector<T>>
class FenwickTreeBase {
public:
FenwickTreeBase() = default;
explicit FenwickTreeBase(index_t n) : n(n) {}
int size() const {
return n;
}
void add(index_t i, T v) {
for (++i; i <= n; i += (i & -i)) data[i - 1] += v;
}
T sum(index_t l, index_t r) const {
return sum(r) - sum(l);
}
auto operator[](int i) {
struct {
int i;
FenwickTreeBase& ft;
operator T() const { return ft.sum(i, i + 1); }
auto& operator++() { return *this += 1; }
auto& operator--() { return *this -= 1; }
auto& operator+=(T val) { ft.add(i, val); return *this; }
auto& operator-=(T val) { ft.add(i, -val); return *this; }
auto& operator*=(T val) { T cur = ft.sum(i, i + 1); ft.add(i, cur * val - cur); return *this; }
auto& operator/=(T val) { T cur = ft.sum(i, i + 1); ft.add(i, cur / val - cur); return *this; }
auto& operator%=(T val) { T cur = ft.sum(i, i + 1); ft.add(i, cur % val - cur); return *this; }
auto& operator =(T val) { T cur = ft.sum(i, i + 1); ft.add(i, val - cur); return *this; }
} obj{ i, *this };
return obj;
}
T operator()(int l, int r) const { return sum(l, r); }
Container& get_internal_container() { return data; }
protected:
index_t n;
Container data;
template <typename ...Args>
FenwickTreeBase(index_t n, Args &&...args) : n(n), data(std::forward<Args>(args)...) {}
private:
T sum(int r) const {
T s{};
for (; r; r -= r & -r) s += data[r - 1];
return s;
}
};
template <typename Key, typename Value, bool unordered>
using cond_map_t = std::conditional_t<unordered, std::unordered_map<Key, Value>, std::map<Key, Value>>;
} // namespace internal
template <typename T>
struct FenwickTree : public internal::FenwickTreeBase<T> {
FenwickTree() : FenwickTree(0) {}
explicit FenwickTree(int n) : internal::FenwickTreeBase<T>::FenwickTreeBase(n, n, T{}) {}
explicit FenwickTree(std::vector<T>&& a) : internal::FenwickTreeBase<T>::FenwickTreeBase(a.size(), std::move(a)) {
for (int i = 1; i <= this->n; ++i) {
int p = i + (i & -i);
if (p <= this->n) this->data[p - 1] += this->data[i - 1];
}
}
explicit FenwickTree(const std::vector<T>& a) : FenwickTree(std::vector<T>(a)) {}
};
template <typename T, typename index_t, bool use_unordered_map = false>
using MapFenwickTree = internal::FenwickTreeBase<T, index_t, internal::cond_map_t<index_t, T, use_unordered_map>>;
} // namespace suisen
#line 8 "library/datastructure/fenwick_tree/static_rectangle_add_rectangle_sum.hpp"
namespace suisen {
template <typename T>
struct AddQuery {
int l, r, d, u;
T val;
AddQuery() = default;
AddQuery(int l, int r, int d, int u, const T &val) : l(l), r(r), d(d), u(u), val(val) {}
};
struct SumQuery {
int l, r, d, u;
SumQuery() = default;
SumQuery(int l, int r, int d, int u) : l(l), r(r), d(d), u(u) {}
};
template <typename T>
std::vector<T> static_rectangle_add_rectangle_sum(const std::vector<AddQuery<T>>& add_queries, const std::vector<SumQuery>& sum_queries) {
using suffix_add_query_type = std::tuple<int, int, T>; // l, d, val
using prefix_sum_query_type = std::tuple<int, int, int, bool>; // r, u, query_id, sign
std::vector<int> ys;
std::vector<suffix_add_query_type> suf_add_queries;
for (const auto& q : add_queries) {
ys.push_back(q.d), ys.push_back(q.u);
suf_add_queries.emplace_back(q.l, q.d, q.val), suf_add_queries.emplace_back(q.r, q.d, -q.val);
suf_add_queries.emplace_back(q.l, q.u, -q.val), suf_add_queries.emplace_back(q.r, q.u, q.val);
}
std::sort(ys.begin(), ys.end());
ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
auto compress = [&ys](int y) -> int { return std::lower_bound(ys.begin(), ys.end(), y) - ys.begin(); };
std::vector<prefix_sum_query_type> pre_sum_queries;
for (std::size_t i = 0; i < sum_queries.size(); ++i) {
const auto& q = sum_queries[i];
pre_sum_queries.emplace_back(q.l, q.d, i, true), pre_sum_queries.emplace_back(q.r, q.d, i, false);
pre_sum_queries.emplace_back(q.l, q.u, i, false), pre_sum_queries.emplace_back(q.r, q.u, i, true);
}
static constexpr auto x_comparator = [](const auto& q1, const auto& q2) { return std::get<0>(q1) < std::get<0>(q2); };
std::sort(suf_add_queries.begin(), suf_add_queries.end(), x_comparator);
std::sort(pre_sum_queries.begin(), pre_sum_queries.end(), x_comparator);
using data_type = std::tuple<T, T, T, T>;
FenwickTree<data_type> ft(ys.size());
std::vector<T> res(sum_queries.size(), T{ 0 });
const int n = suf_add_queries.size(), m = pre_sum_queries.size();
for (int i = 0, j = 0; i < n or j < m;) {
if (j == m or (i < n and std::get<0>(suf_add_queries[i]) < std::get<0>(pre_sum_queries[j]))) {
const auto& [l, d, v] = suf_add_queries[i++];
// v * (x - l) * (y - d) = v * xy - vd * x - vl * y + vld
ft.add(compress(d), data_type{ v, -v * d, -v * l, v * l * d });
} else {
const auto& [x, y, qid, is_add] = pre_sum_queries[j++];
auto [a, b, c, d] = ft.sum(0, compress(y));
const T sum = a * x * y + b * x + c * y + d;
if (is_add) res[qid] += sum;
else res[qid] -= sum;
}
}
return res;
}
} // namespace suisen
#line 10 "test/src/datastructure/fenwick_tree/static_rectangle_add_rectangle_sum/dummy.test.cpp"
using namespace suisen;
template <typename T, int H, int W>
std::vector<T> static_rectangle_add_rectangle_sum_naive(const std::vector<AddQuery<T>>& add_queries, const std::vector<SumQuery>& sum_queries) {
std::array<std::array<T, H>, W> dat;
for (auto& row : dat) row.fill(T{ 0 });
for (const auto& q : add_queries) {
for (int x = q.l; x < q.r; ++x) for (int y = q.d; y < q.u; ++y) {
dat[x][y] += q.val;
}
}
std::vector<T> res(sum_queries.size(), T{ 0 });
for (std::size_t query_id = 0; query_id < sum_queries.size(); ++query_id) {
const auto& q = sum_queries[query_id];
mint& ans = res[query_id];
for (int x = q.l; x < q.r; ++x) for (int y = q.d; y < q.u; ++y) {
ans += dat[x][y];
}
}
return res;
}
template <int H, int W, int AddQ, int SumQ>
void random_test(uint32_t seed = ~uint32_t(0)) {
std::mt19937 rng{ seed != ~uint32_t(0) ? seed : std::random_device{}() };
std::vector<AddQuery<mint>> add_queries(AddQ);
std::vector<SumQuery> sum_queries(SumQ);
std::uniform_int_distribution<int> dist_x(0, H - 1), dist_y(0, W - 1), dist_val(0, mint::mod() - 1);
for (int i = 0; i < AddQ; ++i) {
int l = dist_x(rng), r = dist_x(rng);
if (l > r) std::swap(l, r);
int d = dist_y(rng), u = dist_y(rng);
if (d > u) std::swap(d, u);
int val = dist_val(rng);
add_queries[i] = { l, r, d, u, val };
}
for (int i = 0; i < SumQ; ++i) {
int l = dist_x(rng), r = dist_x(rng);
if (l > r) std::swap(l, r);
int d = dist_y(rng), u = dist_y(rng);
if (d > u) std::swap(d, u);
sum_queries[i] = { l, r, d, u };
}
auto actual = static_rectangle_add_rectangle_sum(add_queries, sum_queries);
auto expected = static_rectangle_add_rectangle_sum_naive<mint, H, W>(add_queries, sum_queries);
assert(actual == expected);
}
int main() {
random_test<1000, 1000, 1000, 1000>();
std::cout << "Hello World" << std::endl;
return 0;
}