Artifact a0dd84df47a73891341ee803993c750cd094848c
//-------------------------------------------------------------
// Range Minimum Query
// O(N log N) construction
// O(1) per each query
// returns the LEFTMOST/ALL minimum index (I hope)
//
// Verified by
// - SRM337 Div1 LV2
// - SRM431 Div1 LV3
//-------------------------------------------------------------
template<typename T>
struct RMQ
{
vector< vector<int> > rm;
vector<T> d;
RMQ( const vector<T>& d ) : d(d) {
int n = d.size();
// rm[k][x] = i s.t. d[i] is the minimum in [x, x+2^k)
rm.push_back( vector<int>(n) );
for(int x=0; x<n; ++x)
rm[0][x] = x;
for(int k=1; (1<<k)<=n; ++k) {
rm.push_back( rm[k-1] );
for(int x=0; x+(1<<k-1)<n; ++x)
if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] )
rm[k][x] = rm[k-1][x + (1<<k-1)];
}
}
int operator()(int L, int R) const { // inclusive
int k=0;
for(; L+(1<<k) < R-(1<<k)+1; ++k) {}
LL i = rm[k][L];
LL j = rm[k][R-(1<<k)+1];
return (d[i]<=d[j] ? i : j);
}
vector<int> all(int L, int R) const {
vector<int> ans;
int minValue = d[(*this)(L, R)];
while( L <= R ) {
int C = (*this)(L, R);
if( minValue < d[C] )
break;
ans.push_back(C);
L = C+1;
}
return ans;
}
};