データ構造/Fenwick tree/2次元 Fenwick tree
(test/data_structure/fenwick_tree/2d_fenwick_tree.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2842

Depends on

• 2次元 Fenwick tree (include/emthrm/data_structure/fenwick_tree/2d_fenwick_tree.hpp)

Code

/*
 * @title データ構造/Fenwick tree/2次元 Fenwick tree
 *
 * verification-helper: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2842
 */

#include <iostream>
#include <tuple>
#include <queue>

#include "emthrm/data_structure/fenwick_tree/2d_fenwick_tree.hpp"

int main() {
  int h, w, t, q;
  std::cin >> h >> w >> t >> q;
  emthrm::FenwickTree2D<int> baked(h, w), unbaked(h, w);
  std::queue<std::tuple<int, int, int>> que;
  while (q--) {
    int t_i, c, h_1, w_1;
    std::cin >> t_i >> c >> h_1 >> w_1;
    --h_1; --w_1;
    while (!que.empty() && std::get<0>(que.front()) <= t_i) {
      const int y = std::get<1>(que.front()), x = std::get<2>(que.front());
      que.pop();
      unbaked.add(y, x, -1);
      baked.add(y, x, 1);
    }
    if (c == 0) {
      unbaked.add(h_1, w_1, 1);
      que.emplace(t_i + t, h_1, w_1);
    } else if (c == 1) {
      if (baked.get(h_1, w_1) == 1) baked.add(h_1, w_1, -1);
    } else if (c == 2) {
      int h_2, w_2;
      std::cin >> h_2 >> w_2;
      --h_2; --w_2;
      std::cout << baked.sum(h_1, w_1, h_2, w_2) << ' '
                << unbaked.sum(h_1, w_1, h_2, w_2) << '\n';
    }
  }
  return 0;
}

#line 1 "test/data_structure/fenwick_tree/2d_fenwick_tree.test.cpp"
/*
 * @title データ構造/Fenwick tree/2次元 Fenwick tree
 *
 * verification-helper: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2842
 */

#include <iostream>
#include <tuple>
#include <queue>

#line 1 "include/emthrm/data_structure/fenwick_tree/2d_fenwick_tree.hpp"



#include <vector>

namespace emthrm {

template <typename Abelian>
struct FenwickTree2D {
  explicit FenwickTree2D(
      const int height_, const int width_, const Abelian ID = 0)
      : height(height_ + 1), width(width_ + 1), ID(ID) {
    data.assign(height, std::vector<Abelian>(width, ID));
  }

  void add(int y, int x, const Abelian val) {
    ++y; ++x;
    for (int i = y; i < height; i += i & -i) {
      for (int j = x; j < width; j += j & -j) {
        data[i][j] += val;
      }
    }
  }

  Abelian sum(int y, int x) const {
    ++y; ++x;
    Abelian res = ID;
    for (int i = y; i > 0; i -= i & -i) {
      for (int j = x; j > 0; j -= j & -j) {
        res += data[i][j];
      }
    }
    return res;
  }

  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);
  }

  Abelian get(const int y, const int x) const { return sum(y, x, y, x); }

 private:
  const int height, width;
  const Abelian ID;
  std::vector<std::vector<Abelian>> data;
};

}  // namespace emthrm


#line 12 "test/data_structure/fenwick_tree/2d_fenwick_tree.test.cpp"

int main() {
  int h, w, t, q;
  std::cin >> h >> w >> t >> q;
  emthrm::FenwickTree2D<int> baked(h, w), unbaked(h, w);
  std::queue<std::tuple<int, int, int>> que;
  while (q--) {
    int t_i, c, h_1, w_1;
    std::cin >> t_i >> c >> h_1 >> w_1;
    --h_1; --w_1;
    while (!que.empty() && std::get<0>(que.front()) <= t_i) {
      const int y = std::get<1>(que.front()), x = std::get<2>(que.front());
      que.pop();
      unbaked.add(y, x, -1);
      baked.add(y, x, 1);
    }
    if (c == 0) {
      unbaked.add(h_1, w_1, 1);
      que.emplace(t_i + t, h_1, w_1);
    } else if (c == 1) {
      if (baked.get(h_1, w_1) == 1) baked.add(h_1, w_1, -1);
    } else if (c == 2) {
      int h_2, w_2;
      std::cin >> h_2 >> w_2;
      --h_2; --w_2;
      std::cout << baked.sum(h_1, w_1, h_2, w_2) << ' '
                << unbaked.sum(h_1, w_1, h_2, w_2) << '\n';
    }
  }
  return 0;
}

Back to top page