C++ Library for Competitive Programming
/*
* @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;
}