データ構造/Fenwick tree/区間加算クエリ対応2次元 Fenwick tree
(test/data_structure/fenwick_tree/2d_fenwick_tree_supporting_range_add_query.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: https://yukicoder.me/problems/no/1490

Depends on

• 区間加算クエリ対応2次元 Fenwick tree (include/emthrm/data_structure/fenwick_tree/2d_fenwick_tree_supporting_range_add_query.hpp)

Code

/*
 * @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;
}

Back to top page