This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/icpc_library
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq" #include "../../data_structure/sparse_table.hpp" #include "../../template/template.hpp" using namespace lib; int op(int a, int b) { return min(a, b); } int main() { int n, q; cin >> n >> q; vector<int> a(n); rep(i, 0, n) cin >> a[i]; SparseTable<int, op> spt(a); while (q--) { int l, r; cin >> l >> r; cout << spt.get(l, r) << '\n'; } }
#line 1 "test/data_structure/StaticRMQ.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/staticrmq" #line 2 "data_structure/sparse_table.hpp" #line 2 "template/template.hpp" #include <bits/stdc++.h> #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) #define all(v) v.begin(), v.end() using ll = long long; using ld = long double; using ull = unsigned long long; template <typename T> bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template <typename T> bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } namespace lib { using namespace std; } // namespace lib // using namespace lib; #line 4 "data_structure/sparse_table.hpp" namespace lib { template <class S, S (*op)(S, S)> struct SparseTable { vector<vector<S>> table; vector<int> clz; SparseTable(const vector<S> &vec) { int n = vec.size(), n2 = 0; while ((1 << n2) < n) n2++; table.resize(n2 + 1); rep(i, 0, n2 + 1) { table[i].resize(n); if (i == 0) { rep(j, 0, n) table[i][j] = vec[j]; } else { rep(j, 0, n) { if (j + (1 << (i - 1)) < n) table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]); else table[i][j] = table[i - 1][j]; } } } clz.resize(n + 1); rep(i, 0, n2 + 1) { for (int j = (1 << i); j < (2 << i) && j <= n; j++) { clz[j] = i; } } } // 単位元を要求しないので if (l >= r) return e() // みたいなことをしていない、注意すること!! S get(int l, int r) { assert(r - l > 0); // int lgs = 31 - __builtin_clz((unsigned int)(r-l)); int lgs = clz[r - l]; return op(table[lgs][l], table[lgs][r - (1 << lgs)]); } }; } // namespace lib #line 5 "test/data_structure/StaticRMQ.test.cpp" using namespace lib; int op(int a, int b) { return min(a, b); } int main() { int n, q; cin >> n >> q; vector<int> a(n); rep(i, 0, n) cin >> a[i]; SparseTable<int, op> spt(a); while (q--) { int l, r; cin >> l >> r; cout << spt.get(l, r) << '\n'; } }