#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2842"
#include <iostream>
#include <queue>
#include <tuple>
#include "Mylib/AlgebraicStructure/Monoid/sum.cpp"
#include "Mylib/DataStructure/SegmentTree/segment_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::segment_tree_2d<hl::sum_monoid<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.segment_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/Monoid/sum.cpp"
namespace haar_lib {
template <typename T>
struct sum_monoid {
using value_type = T;
value_type operator()() const { return 0; }
value_type operator()(value_type a, value_type b) const { return a + b; }
};
} // namespace haar_lib
#line 2 "Mylib/DataStructure/SegmentTree/segment_tree_2d.cpp"
#include <vector>
namespace haar_lib {
template <typename Monoid>
class segment_tree_2d {
public:
using value_type = typename Monoid::value_type;
private:
Monoid M_;
int w_, h_;
std::vector<std::vector<value_type>> data_;
value_type get_w(int l, int r, int y) const {
l += w_ / 2;
r += w_ / 2;
value_type ret = M_();
while (l < r) {
if (r & 1) ret = M_(ret, data_[--r][y]);
if (l & 1) ret = M_(ret, data_[l++][y]);
l >>= 1, r >>= 1;
}
return ret;
}
public:
segment_tree_2d() {}
segment_tree_2d(int width, int height) {
w_ = 1;
while (w_ < width) w_ *= 2;
w_ = w_ * 2;
h_ = 1;
while (h_ < height) h_ *= 2;
h_ = h_ * 2;
data_ = std::vector(w_, std::vector<value_type>(h_, M_()));
}
value_type fold(std::pair<int, int> p1, std::pair<int, int> p2) const {
const auto [x1, y1] = p1;
const auto [x2, y2] = p2;
int l = y1 + h_ / 2;
int r = y2 + h_ / 2;
value_type ret = M_();
while (l < r) {
if (r & 1) ret = M_(ret, get_w(x1, x2, --r));
if (l & 1) ret = M_(ret, get_w(x1, x2, l++));
l >>= 1, r >>= 1;
}
return ret;
}
value_type operator[](std::pair<int, int> p) const {
auto [x, y] = p;
return data_[w_ / 2 + x][h_ / 2 + y];
}
void set(std::pair<int, int> p, const value_type &val) {
const auto [x, y] = p;
const int i = x + w_ / 2;
const int j = y + h_ / 2;
data_[i][j] = val;
for (int X = i >> 1, Y = j; X > 0; X >>= 1) {
data_[X][Y] = M_(data_[X << 1 | 0][Y], data_[X << 1 | 1][Y]);
}
for (int Y = j >> 1; Y > 0; Y >>= 1) {
for (int X = i; X > 0; X >>= 1) {
data_[X][Y] = M_(data_[X][Y << 1 | 0], data_[X][Y << 1 | 1]);
}
}
}
void update(std::pair<int, int> p, const value_type &val) {
set(p, M_((*this)[p], 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.segment_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::segment_tree_2d<hl::sum_monoid<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.segment_tree.test.cpp
Sum monoid
(Mylib/AlgebraicStructure/Monoid/sum.cpp)