This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq" #include <iostream> #include <limits> #include "../../data_type/min_monoid.hpp" #include "../../sparse_table/sparse_table.hpp" using namespace std; using llong = long long; llong n, q; vector<llong> a; int main() { cin >> n >> q; a.resize(n); for (auto &v : a) cin >> v; SparseTable<MinMonoid<llong>> rmq(a.begin(), a.end()); while (q--) { llong l, r; cin >> l >> r; cout << rmq.fold(l, r) << '\n'; } return 0; }
#line 1 "test/yosupo/static_rmq.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/staticrmq" #include <iostream> #include <limits> #line 1 "data_type/min_monoid.hpp" #include <algorithm> #line 6 "data_type/min_monoid.hpp" #include <numeric> //=== template <class T> struct MinMonoid { using value_type = T; inline static T identity() { return std::numeric_limits<T>::max(); }; inline static T operation(const T a, const T b) { return std::min(a, b); }; }; //=== #line 1 "sparse_table/sparse_table.hpp" #include <functional> #include <iterator> #include <vector> //=== template <class SemiLattice> struct SparseTable { using S = SemiLattice; using T = typename SemiLattice::value_type; std::vector<std::vector<T>> table; std::vector<size_t> log2; SparseTable() = default; template <class InputItr> SparseTable(InputItr first, InputItr last) { int n = std::distance(first, last); log2.assign(n + 1, 0); for (int i = 2; i <= n; i++) log2[i] = log2[i / 2] + 1; table.reserve(log2[n] + 1); table.emplace_back(first, last); for (int i = 1; (1 << i) <= n; i++) { int w = 1 << (i - 1); table.emplace_back(); table.back().reserve(n - (1 << i) + 1); for (int j = 0; j + (1 << i) <= n; j++) { table[i].emplace_back( S::operation(table[i - 1][j], table[i - 1][j + w])); } } }; //[l, r) T fold(int l, int r) { int k = log2[r - l]; return S::operation(table[k][l], table[k][r - (1 << k)]); }; int size() { return table[0].size(); }; T operator[](const int k) { return table[0][k]; }; }; //=== #line 8 "test/yosupo/static_rmq.test.cpp" using namespace std; using llong = long long; llong n, q; vector<llong> a; int main() { cin >> n >> q; a.resize(n); for (auto &v : a) cin >> v; SparseTable<MinMonoid<llong>> rmq(a.begin(), a.end()); while (q--) { llong l, r; cin >> l >> r; cout << rmq.fold(l, r) << '\n'; } return 0; }