This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
#ifndef call_from_test #include <bits/stdc++.h> 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 1 "datastructure/sparsetable.cpp" #include <bits/stdc++.h> 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