Artifact b1b5e925fa550aa02370d2768fa3ae40a0742c90

• File lib/dataStructure/rmq.cpp
  • 2012-07-22 18:00:41 - part of checkin [cd0467fefc] on branch trunk - Suffix Array. (user: kinaba) [annotate]

//-------------------------------------------------------------
// Range Minimum Query
//   O(N log N) construction
//   O(log N) per each query
//
// Verified by
//   - SRM337 Div1 LV2
//   - SRM431 Div1 LV3
//   - Codeforces 129 Div1 E
//-------------------------------------------------------------

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)];
		}
	}

	// min {i in [L,R] | d[i] is minumum among d[L..R]}
	int operator()(int L, int R) const {
		int k=0;
		for(; L+(1<<k) < R-(1<<k)+1; ++k) {}
		int i = rm[k][L];
		int j = rm[k][R-(1<<k)+1];
		return (d[i]<=d[j] ? i : j);
	}

	// {i in [L,R] | d[i] is minumum among d[L..R]}
	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;
	}

	// max {i in [L,R] | d[i]<X}, or -1
	int rightmost_less_than_X(int L, int R, T X) const {
		if(L>R) return -1;

		int k=0;
		for(; L+(1<<k) < R-(1<<k)+1; ++k) {}

		int i = rm[k][L];
		int j = rm[k][R-(1<<k)+1];
		if( !(d[i]<X || d[j]<X) )
			return -1;
		if( d[j] < X )
			L = R-(1<<k)+1;

		for(; k; --k) { // Answer is in [L, L+(1<<k))
			i = rm[k-1][L];
			j = rm[k-1][L+(1<<k-1)];
			if( d[j] < X )
				L += 1<<k-1;
		}
		return L;
	}

	// min {i in [L,R] | d[i]<X}, or -1
	int leftmost_less_than_X(int L, int R, T X) const {
		if(L>R) return -1;

		int k=0;
		for(; L+(1<<k) < R-(1<<k)+1; ++k) {}

		int i = rm[k][L];
		int j = rm[k][R-(1<<k)+1];
		if( !(d[i]<X || d[j]<X) )
			return -1;
		if( !(d[i] < X) )
			L = R-(1<<k)+1;

		for(; k; --k) { // Answer is in [L, L+(1<<k))
			i = rm[k-1][L];
			j = rm[k-1][L+(1<<k-1)];
			if( !(d[i] < X) )
				L += 1<<k-1;
		}
		return L;
	}
};