This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq" #include <bits/stdc++.h> using namespace std; #include "../rmq.hpp" signed main() { ios::sync_with_stdio(false), cin.tie(0); int n, q; cin >> n >> q; vector<int> a(n); for (auto &x : a) cin >> x; rmq<int, range_min> st(a); while (q--) { int l, r; cin >> l >> r; cout << st.get(l, r) << '\n'; } }
#line 1 "data-structure/test/Static_RMQ.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/staticrmq" #include <bits/stdc++.h> using namespace std; #line 1 "data-structure/rmq.hpp" // RMQ using Sparse Table // range_min for min, range_max for max template <class T, T (*op)(T, T)> struct rmq { rmq() = default; rmq(const vector<T>& v) : t{v}, n{(int)v.size()} { for (int k = 1; (1 << k) <= n; ++k) { t.emplace_back(n - (1 << k) + 1); for (int i = 0; i + (1 << k) <= n; ++i) { t[k][i] = op(t[k - 1][i], t[k - 1][i + (1 << (k - 1))]); } } } // get range [l, r-1] // doesn't work for empty range T get(int l, int r) const { assert(0 <= l && l < r && r <= n); int k = __lg(r - l); return op(t[k][l], t[k][r - (1 << k)]); } private: vector<vector<T>> t; int n; }; template <class T> T range_min(T a, T b) { return b < a ? b : a; } template <class T> T range_max(T a, T b) { return a < b ? b : a; } #line 8 "data-structure/test/Static_RMQ.test.cpp" signed main() { ios::sync_with_stdio(false), cin.tie(0); int n, q; cin >> n >> q; vector<int> a(n); for (auto &x : a) cin >> x; rmq<int, range_min> st(a); while (q--) { int l, r; cin >> l >> r; cout << st.get(l, r) << '\n'; } }