This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/staticrmq #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../datastructure/sparsetable.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,q; cin>>n>>q; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; auto f=[](int a,int b){return min(a,b);}; SparseTable<int> rmq(f); rmq.build(as); for(int i=0;i<q;i++){ int l,r; cin>>l>>r; cout<<rmq.query(l,r)<<"\n"; } cout<<flush; return 0; }
#line 1 "test/yosupo/staticrmq.sparsetable.test.cpp" // verification-helper: PROBLEM https://judge.yosupo.jp/problem/staticrmq #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "datastructure/sparsetable.cpp" #line 3 "datastructure/sparsetable.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T> struct SparseTable{ using F = function<T(T, T)>; vector< vector<T> > dat; vector<int> ht; const F f; SparseTable(F f):f(f){} void build(const vector<T> &v){ int n=v.size(),h=1; while((1<<h)<=n) h++; dat.assign(h,vector<T>(n)); ht.assign(n+1,0); for(int j=2;j<=n;j++) ht[j]=ht[j>>1]+1; for(int j=0;j<n;j++) dat[0][j]=v[j]; for(int i=1,p=1;i<h;i++,p<<=1) for(int j=0;j<n;j++) dat[i][j]=f(dat[i-1][j],dat[i-1][min(j+p,n-1)]); }; T query(int a,int b){ int l=b-a; return f(dat[ht[l]][a],dat[ht[l]][b-(1<<ht[l])]); } }; //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 8 "test/yosupo/staticrmq.sparsetable.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,q; cin>>n>>q; vector<int> as(n); for(int i=0;i<n;i++) cin>>as[i]; auto f=[](int a,int b){return min(a,b);}; SparseTable<int> rmq(f); rmq.build(as); for(int i=0;i<q;i++){ int l,r; cin>>l>>r; cout<<rmq.query(l,r)<<"\n"; } cout<<flush; return 0; }