#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2842"
#include <iostream>
#include <queue>
#include <tuple>
#include "Mylib/AlgebraicStructure/Group/sum.cpp"
#include "Mylib/DataStructure/FenwickTree/fenwick_tree_2d.cpp"
#include "Mylib/IO/input_tuples.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int H, W, T, Q;
std::cin >> H >> W >> T >> Q;
hl::fenwick_tree_2d<hl::sum_group<int>> seg1(H, W), seg2(H, W);
std::queue<std::tuple<int, int, int>> q;
for (auto [t, c] : hl::input_tuples<int, int>(Q)) {
while (q.size()) {
auto &a = q.front();
if (t >= std::get<2>(a) + T) {
int x = std::get<0>(a), y = std::get<1>(a);
seg1.update({x, y}, 1);
seg2.update({x, y}, -1);
q.pop();
} else {
break;
}
}
if (c == 0) {
int h, w;
std::cin >> h >> w;
--h, --w;
seg2.update({h, w}, 1);
q.emplace(h, w, t);
} else if (c == 1) {
int h, w;
std::cin >> h >> w;
--h, --w;
if (seg1[{h, w}] == 1) seg1.update({h, w}, -1);
} else {
int h1, w1, h2, w2;
std::cin >> h1 >> w1 >> h2 >> w2;
--h1, --w1;
std::cout << seg1.fold({h1, w1}, {h2, w2}) << " " << seg2.fold({h1, w1}, {h2, w2}) << std::endl;
}
}
return 0;
}
#line 1 "test/aoj/2842/main.fenwick_tree.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2842"
#include <iostream>
#include <queue>
#include <tuple>
#line 2 "Mylib/AlgebraicStructure/Group/sum.cpp"
namespace haar_lib {
template <typename T>
struct sum_group {
using value_type = T;
value_type operator()() const { return 0; }
value_type operator()(const value_type &a, const value_type &b) const { return a + b; }
value_type inv(const value_type &a) const { return -a; }
};
} // namespace haar_lib
#line 2 "Mylib/DataStructure/FenwickTree/fenwick_tree_2d.cpp"
#include <cassert>
#include <vector>
namespace haar_lib {
template <typename AbelianGroup>
class fenwick_tree_2d {
public:
using value_type = typename AbelianGroup::value_type;
private:
AbelianGroup G_;
int w_, h_;
std::vector<std::vector<value_type>> data_;
private:
value_type get_w(int i, int y) const {
value_type ret = G_();
while (i > 0) {
ret = G_(ret, data_[i][y]);
i -= i & (-i);
}
return ret;
}
value_type get_w(int l, int r, int y) const {
return G_(get_w(r, y), G_.inv(get_w(l, y)));
}
value_type get(int x1, int x2, int y) const {
value_type ret = G_();
while (y > 0) {
ret = G_(ret, get_w(x1, x2, y));
y -= y & (-y);
}
return ret;
}
public:
fenwick_tree_2d() {}
fenwick_tree_2d(int width, int height) : w_(width), h_(height), data_(w_ + 1, std::vector<value_type>(h_ + 1, G_())) {}
value_type fold(std::pair<int, int> p1, std::pair<int, int> p2) const {
const auto [x1, y1] = p1;
const auto [x2, y2] = p2;
assert(0 <= x1 and x1 <= x2 and x2 <= w_);
assert(0 <= y1 and y1 <= y2 and y2 <= h_);
return G_(get(x1, x2, y2), G_.inv(get(x1, x2, y1)));
}
value_type operator[](std::pair<int, int> p) const {
const auto [x, y] = p;
return fold({x, y}, {x + 1, y + 1});
}
void update(std::pair<int, int> p, const value_type &val) {
auto [x, y] = p;
assert(0 <= x and x < w_);
assert(0 <= y and y < h_);
x += 1;
y += 1;
for (int i = x; i <= w_; i += i & (-i)) {
for (int j = y; j <= h_; j += j & (-j)) {
data_[i][j] = G_(data_[i][j], val);
}
}
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 5 "Mylib/IO/input_tuples.cpp"
#include <utility>
#line 6 "Mylib/IO/input_tuple.cpp"
namespace haar_lib {
template <typename T, size_t... I>
static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
}
template <typename T, typename U>
std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
s >> value.first >> value.second;
return s;
}
template <typename... Args>
std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
return s;
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuples {
struct iter {
using value_type = std::tuple<Args...>;
value_type value;
bool fetched = false;
int N, c = 0;
value_type operator*() {
if (not fetched) {
std::cin >> value;
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuples(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples(int N) {
return InputTuples<Args...>(N);
}
} // namespace haar_lib
#line 9 "test/aoj/2842/main.fenwick_tree.test.cpp"
namespace hl = haar_lib;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int H, W, T, Q;
std::cin >> H >> W >> T >> Q;
hl::fenwick_tree_2d<hl::sum_group<int>> seg1(H, W), seg2(H, W);
std::queue<std::tuple<int, int, int>> q;
for (auto [t, c] : hl::input_tuples<int, int>(Q)) {
while (q.size()) {
auto &a = q.front();
if (t >= std::get<2>(a) + T) {
int x = std::get<0>(a), y = std::get<1>(a);
seg1.update({x, y}, 1);
seg2.update({x, y}, -1);
q.pop();
} else {
break;
}
}
if (c == 0) {
int h, w;
std::cin >> h >> w;
--h, --w;
seg2.update({h, w}, 1);
q.emplace(h, w, t);
} else if (c == 1) {
int h, w;
std::cin >> h >> w;
--h, --w;
if (seg1[{h, w}] == 1) seg1.update({h, w}, -1);
} else {
int h1, w1, h2, w2;
std::cin >> h1 >> w1 >> h2 >> w2;
--h1, --w1;
std::cout << seg1.fold({h1, w1}, {h2, w2}) << " " << seg2.fold({h1, w1}, {h2, w2}) << std::endl;
}
}
return 0;
}
test/aoj/2842/main.fenwick_tree.test.cpp
Sum group
(Mylib/AlgebraicStructure/Group/sum.cpp)