test/data-structure/sparse-table/yosupo-Static-RMQ.test.cpp

View this file on GitHub
Last update: 2023-07-11 10:41:16+08:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

library/data-structure/sparse-table.hpp

Code

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

#include <iostream>

#include <vector>

#include <algorithm>

#include "../../../library/data-structure/sparse-table.hpp"

using namespace std;
using namespace felix;

int op_min(int a, int b) {
	return min(a, b);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sparse_table<int, op_min> st(a);
	while(q--) {
		int l, r;
		cin >> l >> r;
		--r;
		cout << st.prod(l, r) << "\n";
	}
	return 0;
}

#line 1 "test/data-structure/sparse-table/yosupo-Static-RMQ.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include <iostream>

#include <vector>

#include <algorithm>

#line 3 "library/data-structure/sparse-table.hpp"
#include <cassert>

namespace felix {

template<class S, S (*op)(S, S)>
struct sparse_table {
public:
	sparse_table() {}
	explicit sparse_table(const std::vector<S>& a) {
		n = (int) a.size();
		int max_log = std::__lg(n) + 1;
		mat.resize(max_log);
		mat[0] = a;
		for(int j = 1; j < max_log; ++j) {
			mat[j].resize(n - (1 << j) + 1);
			for(int i = 0; i <= n - (1 << j); ++i) {
				mat[j][i] = op(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
			}
		}
	}

	S prod(int from, int to) const {
		assert(0 <= from && from <= to && to <= n - 1);
		int lg = std::__lg(to - from + 1);
		return op(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
	}

private:
	int n;
	std::vector<std::vector<S>> mat;
};

} // namespace felix
#line 7 "test/data-structure/sparse-table/yosupo-Static-RMQ.test.cpp"
using namespace std;
using namespace felix;

int op_min(int a, int b) {
	return min(a, b);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sparse_table<int, op_min> st(a);
	while(q--) {
		int l, r;
		cin >> l >> r;
		--r;
		cout << st.prod(l, r) << "\n";
	}
	return 0;
}