test/sparseTable.test.cpp

• View this file on GitHub
• Last update: 2023-03-06 15:21:58+09:00
• Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• sparseTable ( $x \oplus x\ =\ x$ の区間クエリ解答 ) (src/dataStructure/sparseTable.hpp)
• minStructure (Sparse Table) (src/utility/sparseTable/minStructure.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include "../src/dataStructure/sparseTable.hpp"
#include "../src/utility/sparseTable/minStructure.hpp"

#include <iostream>

int main() {
	int N, Q; std::cin >> N >> Q;
	std::vector<int> A(N, 0);
	for (auto& a : A) {
		std::cin >> a;
	}
	zawa::sparseTable<zawa::minStructure<int>> S(A);
	for (int _ = 0 ; _ < Q ; _++) {
		int l, r; std::cin >> l >> r;
		std::cout << S.query(l, r) << std::endl;
	}
}

#line 1 "test/sparseTable.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#line 2 "src/dataStructure/sparseTable.hpp"

#include <vector>
#include <cassert>

namespace zawa {

template <class structure>
class sparseTable {
private:
	using T = typename structure::valueType;
	std::vector<int> L;
	std::vector<std::vector<T>> dat;

public:

	sparseTable(const std::vector<T>& A) : L(A.size() + 1, 0) {
		for (int i = 1 ; i < (int)L.size() ; i++) {
			L[i] = L[i - 1] + (i >> (L[i - 1] + 1));
		}
		dat = std::vector(L.back() + 1, A);
		for (int i = 1 ; i < (int)dat.size() ; i++) {
			int pt = (1 << i);
			for (int j = 0 ; j + pt - 1 < (int)dat[i].size() ; j++) {
				dat[i][j] = structure::operation(dat[i - 1][j], dat[i - 1][j + (pt >> 1)]);
			}
		}
	}

	T query(int l, int r) {
		assert(0 <= l and l < (int)dat[0].size());
		assert(l <= r and r <= (int)dat[0].size());
		int now = L[r - l];
		return structure::operation(dat[now][l], dat[now][r - (1 << now)]);
	}

	inline std::vector<std::vector<T>> _dat() const {
		return dat;
	}

};

} // namespace zawa
#line 2 "src/utility/sparseTable/minStructure.hpp"

#include <algorithm>

namespace zawa {

template <class T>
struct minStructure {
	using valueType = T;
	static valueType operation(const valueType& a, const valueType& b) {
		return std::min(a, b);
	}
};

} // namespace zawa
#line 5 "test/sparseTable.test.cpp"

#include <iostream>

int main() {
	int N, Q; std::cin >> N >> Q;
	std::vector<int> A(N, 0);
	for (auto& a : A) {
		std::cin >> a;
	}
	zawa::sparseTable<zawa::minStructure<int>> S(A);
	for (int _ = 0 ; _ < Q ; _++) {
		int l, r; std::cin >> l >> r;
		std::cout << S.query(l, r) << std::endl;
	}
}

Back to top page