This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub shibh308/library
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq" #include <bits/stdc++.h> using namespace std; using i64 = long; #include "../lib/classes/disjointsparsetable.cpp" signed main() { int n, q; scanf("%d%d", &n, &q); vector<int> a(n); for(auto& x : a) cin >> x; DisjointSparseTable<int> d(a, [](auto x, auto y){return min(x, y);}); for(int i = 0; i < q; ++i){ int l, r; cin >> l >> r; cout << d.get(l, r) << endl; } }
#line 1 "verify/static_rmq.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/staticrmq" #include <bits/stdc++.h> using namespace std; using i64 = long; #line 1 "lib/classes/disjointsparsetable.cpp" template <typename T> struct DisjointSparseTable{ function<T(T, T)> f; vector<vector<T>> v; DisjointSparseTable(vector<T>& inp, function<T(T, T)> f) : f(f){ int n = inp.size(); int b; for(b = 0; (1 << b) <= inp.size(); ++b); v.assign(b, vector<T>(n)); for(int i = 0; i < n; ++i) v[0][i] = inp[i]; for(int i = 1; i < b; ++i){ int siz = 1 << i; for(int j = 0; j < n; j += siz << 1){ int t = min(j + siz, n); v[i][t - 1] = inp[t - 1]; for(int k = t - 2; k >= j; --k) v[i][k] = f(inp[k], v[i][k + 1]); if(t >= n) break; v[i][t] = inp[t]; int r = min(t + siz, n); for(int k = t + 1; k < r; ++k) v[i][k] = f(v[i][k - 1], inp[k]); } } } T get(int l, int r){ if(l >= --r) return v[0][l]; int p = 31 - __builtin_clz(l ^ r); return f(v[p][l], v[p][r]); } }; #line 8 "verify/static_rmq.test.cpp" signed main() { int n, q; scanf("%d%d", &n, &q); vector<int> a(n); for(auto& x : a) cin >> x; DisjointSparseTable<int> d(a, [](auto x, auto y){return min(x, y);}); for(int i = 0; i < q; ++i){ int l, r; cin >> l >> r; cout << d.get(l, r) << endl; } }