C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title データ構造/Fenwick tree/区間加算クエリ対応2次元 Fenwick tree * * verification-helper: PROBLEM https://yukicoder.me/problems/no/1490 */ #include <algorithm> #include <iostream> #include <vector> #include "emthrm/data_structure/fenwick_tree/2d_fenwick_tree_supporting_range_add_query.hpp" int main() { int h, w, n, m; std::cin >> h >> w >> n >> m; std::vector<int> t(n), u(n), l(n), r(n), a(n); for (int i = 0; i < n; ++i) { std::cin >> t[i] >> u[i] >> l[i] >> r[i] >> a[i]; --t[i]; --u[i]; --l[i]; --r[i]; } emthrm::FenwickTree2DSupportingRangeAddQuery<long long> bit(h, w); while (m--) { int x, y, b, c; std::cin >> x >> y >> b >> c; --x; --y; bit.add(std::max(x - b, 0), std::max(y - b, 0), std::min(x + b, h - 1), std::min(y + b, w - 1), c); } int ans = 0; for (int i = 0; i < n; ++i) { ans += bit.sum(t[i], l[i], u[i], r[i]) < a[i]; } std::cout << ans << '\n'; return 0; }
#line 1 "test/data_structure/fenwick_tree/2d_fenwick_tree_supporting_range_add_query.test.cpp" /* * @title データ構造/Fenwick tree/区間加算クエリ対応2次元 Fenwick tree * * verification-helper: PROBLEM https://yukicoder.me/problems/no/1490 */ #include <algorithm> #include <iostream> #include <vector> #line 1 "include/emthrm/data_structure/fenwick_tree/2d_fenwick_tree_supporting_range_add_query.hpp" #line 5 "include/emthrm/data_structure/fenwick_tree/2d_fenwick_tree_supporting_range_add_query.hpp" namespace emthrm { template <typename Abelian> struct FenwickTree2DSupportingRangeAddQuery { explicit FenwickTree2DSupportingRangeAddQuery( const int height_, const int width_, const Abelian ID = 0) : height(height_ + 1), width(width_ + 1), ID(ID) { data_const.assign(height, std::vector<Abelian>(width, ID)); data_linear[0].assign(height, std::vector<Abelian>(width, ID)); data_linear[1].assign(height, std::vector<Abelian>(width, ID)); data_quadratic.assign(height, std::vector<Abelian>(width, ID)); } void add(int y1, int x1, int y2, int x2, const Abelian val) { ++y1; ++x1; ++y2; ++x2; for (int i = y1; i < height; i += i & -i) { for (int j = x1; j < width; j += j & -j) { data_const[i][j] += val * (y1 - 1) * (x1 - 1); data_linear[0][i][j] -= val * (x1 - 1); data_linear[1][i][j] -= val * (y1 - 1); data_quadratic[i][j] += val; } } for (int i = y1; i < height; i += i & -i) { for (int j = x2 + 1; j < width; j += j & -j) { data_const[i][j] -= val * (y1 - 1) * x2; data_linear[0][i][j] += val * x2; data_linear[1][i][j] += val * (y1 - 1); data_quadratic[i][j] -= val; } } for (int i = y2 + 1; i < height; i += i & -i) { for (int j = x1; j < width; j += j & -j) { data_const[i][j] -= val * y2 * (x1 - 1); data_linear[0][i][j] += val * (x1 - 1); data_linear[1][i][j] += val * y2; data_quadratic[i][j] -= val; } } for (int i = y2 + 1; i < height; i += i & -i) { for (int j = x2 + 1; j < width; j += j & -j) { data_const[i][j] += val * y2 * x2; data_linear[0][i][j] -= val * x2; data_linear[1][i][j] -= val * y2; data_quadratic[i][j] += val; } } } Abelian sum(int y, int x) const { ++y; ++x; Abelian quad = ID, cons = ID, line[2]{ID, ID}; for (int i = y; i > 0; i -= i & -i) { for (int j = x; j > 0; j -= j & -j) { quad += data_quadratic[i][j]; line[0] += data_linear[0][i][j]; line[1] += data_linear[1][i][j]; cons += data_const[i][j]; } } return quad * y * x + line[0] * y + line[1] * x + cons; } Abelian sum(const int y1, const int x1, const int y2, const int x2) const { return y1 > y2 || x1 > x2 ? ID : sum(y2, x2) - sum(y2, x1 - 1) - sum(y1 - 1, x2) + sum(y1 - 1, x1 - 1); } private: const int height, width; const Abelian ID; std::vector<std::vector<Abelian>> data_const, data_quadratic; std::vector<std::vector<Abelian>> data_linear[2]; }; } // namespace emthrm #line 12 "test/data_structure/fenwick_tree/2d_fenwick_tree_supporting_range_add_query.test.cpp" int main() { int h, w, n, m; std::cin >> h >> w >> n >> m; std::vector<int> t(n), u(n), l(n), r(n), a(n); for (int i = 0; i < n; ++i) { std::cin >> t[i] >> u[i] >> l[i] >> r[i] >> a[i]; --t[i]; --u[i]; --l[i]; --r[i]; } emthrm::FenwickTree2DSupportingRangeAddQuery<long long> bit(h, w); while (m--) { int x, y, b, c; std::cin >> x >> y >> b >> c; --x; --y; bit.add(std::max(x - b, 0), std::max(y - b, 0), std::min(x + b, h - 1), std::min(y + b, w - 1), c); } int ans = 0; for (int i = 0; i < n; ++i) { ans += bit.sum(t[i], l[i], u[i], r[i]) < a[i]; } std::cout << ans << '\n'; return 0; }