This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub gyouzasushi/library
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq" #include <iostream> #include "datastructure/sparse_table.hpp" using S = int; S op(S a, S b) { return std::min(a, b); } int main() { int n, q; std::cin >> n >> q; std::vector<S> a(n); for (int i = 0; i < n; i++) std::cin >> a[i]; SparseTable<S, op> s(a); while (q--) { int l, r; std::cin >> l >> r; std::cout << s.prod(l, r) << '\n'; } }
#line 1 "test/library-checker/staticrmq.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/staticrmq" #include <iostream> #line 2 "datastructure/sparse_table.hpp" #include <cassert> #include <vector> template <class S, S (*op)(S, S)> struct SparseTable { public: SparseTable() { } SparseTable(const std::vector<S>& v) : _n(int(v.size())), d(_n), ceil_log2(_n + 1) { ceil_log2[0] = 0; ceil_log2[1] = 0; for (int i = 2; i <= _n; i++) ceil_log2[i] = ceil_log2[i >> 1] + 1; for (int i = 0; i < _n; i++) { d[i].resize(ceil_log2[_n] + 1); d[i][0] = v[i]; } for (int b = 0; b < ceil_log2[_n]; b++) { for (int i = 0; i < _n; i++) { if (i + (1 << (b + 1)) > _n) break; d[i][b + 1] = op(d[i][b], d[i + (1 << b)][b]); } } } S prod(int l, int r) { assert(r - l > 0); int b = ceil_log2[r - l]; return op(d[l][b], d[r - (1 << b)][b]); } private: int _n; std::vector<std::vector<S>> d; std::vector<int> ceil_log2; }; #line 5 "test/library-checker/staticrmq.test.cpp" using S = int; S op(S a, S b) { return std::min(a, b); } int main() { int n, q; std::cin >> n >> q; std::vector<S> a(n); for (int i = 0; i < n; i++) std::cin >> a[i]; SparseTable<S, op> s(a); while (q--) { int l, r; std::cin >> l >> r; std::cout << s.prod(l, r) << '\n'; } }