23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: // Range Minimum Query
23dfcca431 2011-02-23        kinaba: //   O(N log N) construction
cd0467fefc 2012-07-22        kinaba: //   O(log N) per each query
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // Verified by
23dfcca431 2011-02-23        kinaba: //   - SRM337 Div1 LV2
23dfcca431 2011-02-23        kinaba: //   - SRM431 Div1 LV3
cd0467fefc 2012-07-22        kinaba: //   - Codeforces 129 Div1 E
23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: template<typename T>
23dfcca431 2011-02-23        kinaba: struct RMQ
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	vector< vector<int> > rm;
23dfcca431 2011-02-23        kinaba: 	vector<T> d;
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	RMQ( const vector<T>& d ) : d(d) {
23dfcca431 2011-02-23        kinaba: 		int n = d.size();
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 		// rm[k][x] = i s.t. d[i] is the minimum in [x, x+2^k)
23dfcca431 2011-02-23        kinaba: 		rm.push_back( vector<int>(n) );
23dfcca431 2011-02-23        kinaba: 		for(int x=0; x<n; ++x)
23dfcca431 2011-02-23        kinaba: 			rm[0][x] = x;
23dfcca431 2011-02-23        kinaba: 		for(int k=1; (1<<k)<=n; ++k) {
23dfcca431 2011-02-23        kinaba: 			rm.push_back( rm[k-1] );
23dfcca431 2011-02-23        kinaba: 			for(int x=0; x+(1<<k-1)<n; ++x)
23dfcca431 2011-02-23        kinaba: 				if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] )
23dfcca431 2011-02-23        kinaba: 					rm[k][x] = rm[k-1][x + (1<<k-1)];
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: 
cd0467fefc 2012-07-22        kinaba: 	// min {i in [L,R] | d[i] is minumum among d[L..R]}
cd0467fefc 2012-07-22        kinaba: 	int operator()(int L, int R) const {
23dfcca431 2011-02-23        kinaba: 		int k=0;
23dfcca431 2011-02-23        kinaba: 		for(; L+(1<<k) < R-(1<<k)+1; ++k) {}
cd0467fefc 2012-07-22        kinaba: 		int i = rm[k][L];
cd0467fefc 2012-07-22        kinaba: 		int j = rm[k][R-(1<<k)+1];
23dfcca431 2011-02-23        kinaba: 		return (d[i]<=d[j] ? i : j);
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: 
cd0467fefc 2012-07-22        kinaba: 	// {i in [L,R] | d[i] is minumum among d[L..R]}
23dfcca431 2011-02-23        kinaba: 	vector<int> all(int L, int R) const {
23dfcca431 2011-02-23        kinaba: 		vector<int> ans;
23dfcca431 2011-02-23        kinaba: 		int minValue = d[(*this)(L, R)];
23dfcca431 2011-02-23        kinaba: 		while( L <= R ) {
23dfcca431 2011-02-23        kinaba: 			int C = (*this)(L, R);
23dfcca431 2011-02-23        kinaba: 			if( minValue < d[C] )
23dfcca431 2011-02-23        kinaba: 				break;
23dfcca431 2011-02-23        kinaba: 			ans.push_back(C);
23dfcca431 2011-02-23        kinaba: 			L = C+1;
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 		return ans;
cd0467fefc 2012-07-22        kinaba: 	}
cd0467fefc 2012-07-22        kinaba: 
cd0467fefc 2012-07-22        kinaba: 	// max {i in [L,R] | d[i]<X}, or -1
cd0467fefc 2012-07-22        kinaba: 	int rightmost_less_than_X(int L, int R, T X) const {
cd0467fefc 2012-07-22        kinaba: 		if(L>R) return -1;
cd0467fefc 2012-07-22        kinaba: 
cd0467fefc 2012-07-22        kinaba: 		int k=0;
cd0467fefc 2012-07-22        kinaba: 		for(; L+(1<<k) < R-(1<<k)+1; ++k) {}
cd0467fefc 2012-07-22        kinaba: 
cd0467fefc 2012-07-22        kinaba: 		int i = rm[k][L];
cd0467fefc 2012-07-22        kinaba: 		int j = rm[k][R-(1<<k)+1];
cd0467fefc 2012-07-22        kinaba: 		if( !(d[i]<X || d[j]<X) )
cd0467fefc 2012-07-22        kinaba: 			return -1;
cd0467fefc 2012-07-22        kinaba: 		if( d[j] < X )
cd0467fefc 2012-07-22        kinaba: 			L = R-(1<<k)+1;
cd0467fefc 2012-07-22        kinaba: 
cd0467fefc 2012-07-22        kinaba: 		for(; k; --k) { // Answer is in [L, L+(1<<k))
cd0467fefc 2012-07-22        kinaba: 			i = rm[k-1][L];
cd0467fefc 2012-07-22        kinaba: 			j = rm[k-1][L+(1<<k-1)];
cd0467fefc 2012-07-22        kinaba: 			if( d[j] < X )
cd0467fefc 2012-07-22        kinaba: 				L += 1<<k-1;
cd0467fefc 2012-07-22        kinaba: 		}
cd0467fefc 2012-07-22        kinaba: 		return L;
cd0467fefc 2012-07-22        kinaba: 	}
cd0467fefc 2012-07-22        kinaba: 
cd0467fefc 2012-07-22        kinaba: 	// min {i in [L,R] | d[i]<X}, or -1
cd0467fefc 2012-07-22        kinaba: 	int leftmost_less_than_X(int L, int R, T X) const {
cd0467fefc 2012-07-22        kinaba: 		if(L>R) return -1;
cd0467fefc 2012-07-22        kinaba: 
cd0467fefc 2012-07-22        kinaba: 		int k=0;
cd0467fefc 2012-07-22        kinaba: 		for(; L+(1<<k) < R-(1<<k)+1; ++k) {}
cd0467fefc 2012-07-22        kinaba: 
cd0467fefc 2012-07-22        kinaba: 		int i = rm[k][L];
cd0467fefc 2012-07-22        kinaba: 		int j = rm[k][R-(1<<k)+1];
cd0467fefc 2012-07-22        kinaba: 		if( !(d[i]<X || d[j]<X) )
cd0467fefc 2012-07-22        kinaba: 			return -1;
cd0467fefc 2012-07-22        kinaba: 		if( !(d[i] < X) )
cd0467fefc 2012-07-22        kinaba: 			L = R-(1<<k)+1;
cd0467fefc 2012-07-22        kinaba: 
cd0467fefc 2012-07-22        kinaba: 		for(; k; --k) { // Answer is in [L, L+(1<<k))
cd0467fefc 2012-07-22        kinaba: 			i = rm[k-1][L];
cd0467fefc 2012-07-22        kinaba: 			j = rm[k-1][L+(1<<k-1)];
cd0467fefc 2012-07-22        kinaba: 			if( !(d[i] < X) )
cd0467fefc 2012-07-22        kinaba: 				L += 1<<k-1;
cd0467fefc 2012-07-22        kinaba: 		}
cd0467fefc 2012-07-22        kinaba: 		return L;
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: };