Test/BinaryIndexedTree2D.test.cpp

• View this file on GitHub
• Last update: 2021-03-09 16:44:31+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2842

Depends on

• 二次元 Binary Indexed Tree (DataStructure/BinaryIndexedTree2D.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2842"

#include "DataStructure/BinaryIndexedTree2D.hpp"

#include <cstdio>
#include <vector>
#include <queue>
#include <utility>

int main() {
	int H, W, T, Q;
	scanf("%d %d %d %d", &H, &W, &T, &Q);
	std::vector<int> t(Q), c(Q), h1(Q), w1(Q), h2(Q), w2(Q);
	
	using pii = std::pair<int, int>;
	
	std::queue<pii> que; // 焼き上がりの時刻, イベントID

	BinaryIndexedTree2D<int> bit1(H, W), bit2(H, W); // bit1: 焼き上がった, bit2: まだ焼き上がっていない

	
	for (int i = 0; i < Q; ++i) {
		scanf("%d %d %d %d", &t[i], &c[i], &h1[i], &w1[i]);
		--h1[i]; --w1[i];
		
		while (!que.empty() && que.front().first <= t[i]) {
			int idx = que.front().second; que.pop();
			bit2.add(h1[idx], w1[idx], -1);
			bit1.add(h1[idx], w1[idx], 1);
		}
		
		if (c[i] == 0) { // セット

			bit2.add(h1[i], w1[i], 1);
			que.emplace(t[i] + T, i);
		}
		else if (c[i] == 1) { // つまみ食い

			if (bit1.sum(h1[i], h1[i] + 1, w1[i], w1[i] + 1) == 1) bit1.add(h1[i], w1[i], -1);
		}
		else { // カウント

			scanf("%d %d", &h2[i], &w2[i]);
			printf("%d %d\n", bit1.sum(h1[i], h2[i], w1[i], w2[i]), bit2.sum(h1[i], h2[i], w1[i], w2[i]));
		}
	}
}

#line 1 "Test/BinaryIndexedTree2D.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2842"

#line 1 "DataStructure/BinaryIndexedTree2D.hpp"



#include <vector>
#include <cassert>

/**
 * @brief https://tkmst201.github.io/Library/DataStructure/BinaryIndexedTree2D.hpp
 */
template<typename T>
struct BinaryIndexedTree2D {
	static_assert(std::is_integral<T>::value == true);
	
	using value_type = T;
	using size_type = std::size_t;
	
private:
	size_type h, w;
	std::vector<std::vector<value_type>> node;
	
public:
	BinaryIndexedTree2D(size_type h, size_type w)
		: h(h), w(w), node(h + 1, std::vector<value_type>(w + 1)) {}
	
	std::pair<size_type, size_type> size() const noexcept {
		return {h, w};
	}
	
	void add(size_type i, size_type j, value_type x) noexcept {
		assert(i < h);
		assert(j < w);
		++i; ++j;
		for (; i <= h; i += i & -i) {
			for (size_type k = j; k <= w; k += k & -k) {
				node[i][k] += x;
			}
		}
	}
	
	value_type sum(size_type i, size_type j) const noexcept {
		assert(i <= h);
		assert(j <= w);
		value_type res = 0;
		for (; i > 0; i -= i & -i) {
			for (size_type k = j; k > 0; k -= k & -k) {
				res += node[i][k];
			}
		}
		return res;
	}
	
	value_type sum(size_type i1, size_type i2, size_type j1, size_type j2) const noexcept {
		assert(i1 <= i2);
		assert(j1 <= j2);
		assert(i2 <= h);
		assert(j2 <= w);
		if (i1 == i2 || j1 == j2) return 0;
		return sum(i2, j2) - sum(i2, j1) + sum(i1, j1) - sum(i1, j2);
	}
};


#line 4 "Test/BinaryIndexedTree2D.test.cpp"

#include <cstdio>
#line 7 "Test/BinaryIndexedTree2D.test.cpp"
#include <queue>
#include <utility>

int main() {
	int H, W, T, Q;
	scanf("%d %d %d %d", &H, &W, &T, &Q);
	std::vector<int> t(Q), c(Q), h1(Q), w1(Q), h2(Q), w2(Q);
	
	using pii = std::pair<int, int>;
	
	std::queue<pii> que; // 焼き上がりの時刻, イベントID

	BinaryIndexedTree2D<int> bit1(H, W), bit2(H, W); // bit1: 焼き上がった, bit2: まだ焼き上がっていない

	
	for (int i = 0; i < Q; ++i) {
		scanf("%d %d %d %d", &t[i], &c[i], &h1[i], &w1[i]);
		--h1[i]; --w1[i];
		
		while (!que.empty() && que.front().first <= t[i]) {
			int idx = que.front().second; que.pop();
			bit2.add(h1[idx], w1[idx], -1);
			bit1.add(h1[idx], w1[idx], 1);
		}
		
		if (c[i] == 0) { // セット

			bit2.add(h1[i], w1[i], 1);
			que.emplace(t[i] + T, i);
		}
		else if (c[i] == 1) { // つまみ食い

			if (bit1.sum(h1[i], h1[i] + 1, w1[i], w1[i] + 1) == 1) bit1.add(h1[i], w1[i], -1);
		}
		else { // カウント

			scanf("%d %d", &h2[i], &w2[i]);
			printf("%d %d\n", bit1.sum(h1[i], h2[i], w1[i], w2[i]), bit2.sum(h1[i], h2[i], w1[i], w2[i]));
		}
	}
}

Back to top page