verify/staticrmq.test.cpp

View this file on GitHub · Last update: 2026-07-25 01:16:11-07:00

Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

• rmq.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/staticrmq

#include <bits/stdc++.h>
#include <cassert>

#include "rmq.hpp"

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	int N, Q; std::cin >> N >> Q;
	std::vector<int> A(N); for (auto& x : A) std::cin >> x;
	RangeMinQuery<int> rmq(A);
	for (int q = 0; q < Q; q++) {
		int l, r; std::cin >> l >> r;
		std::cout << rmq.query(l, r-1) << '\n';
	}

	return 0;
}

#include <bits/stdc++.h>
#line 1 "verify/staticrmq.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/staticrmq

#line 5 "verify/staticrmq.test.cpp"

#line 2 "src/rmq.hpp"

#line 7 "src/rmq.hpp"

template <typename T, class Compare = std::less<T>> class RangeMinQuery : private Compare {
	static const int BUCKET_SIZE = 32;
	static const int BUCKET_SIZE_LOG = 5;
	static_assert(BUCKET_SIZE == (1 << BUCKET_SIZE_LOG), "BUCKET_SIZE should be a power of 2");
	static const int CACHE_LINE_ALIGNMENT = 64;
	int n = 0;
	std::vector<T> data;
	std::vector<T> pref_data;
	std::vector<T> suff_data;
	std::vector<T> sparse_table;
	std::vector<uint32_t> range_mask;

private:
	int num_buckets() const {
		return n >> BUCKET_SIZE_LOG;
	}
	int num_levels() const {
		return num_buckets() ? 32 - __builtin_clz(num_buckets()) : 0;
	}
	int sparse_table_size() const {
		return num_buckets() * num_levels();
	}
private:
	const T& min(const T& a, const T& b) const {
		return Compare::operator()(a, b) ? a : b;
	}
	void setmin(T& a, const T& b) const {
		if (Compare::operator()(b, a)) a = b;
	}

	template <typename Vec> static int get_size(const Vec& v) { using std::size; return int(size(v)); }

public:
	RangeMinQuery() {}
	template <typename Vec> explicit RangeMinQuery(const Vec& data_, const Compare& comp_ = Compare())
		: Compare(comp_)
		, n(get_size(data_))
		, data(n)
		, pref_data(n)
		, suff_data(n)
		, sparse_table(sparse_table_size())
		, range_mask(n)
	{
		for (int i = 0; i < n; i++) data[i] = data_[i];
		for (int i = 0; i < n; i++) {
			if (i & (BUCKET_SIZE-1)) {
				uint32_t m = range_mask[i-1];
				while (m && !Compare::operator()(data[(i | (BUCKET_SIZE-1)) - __builtin_clz(m)], data[i])) {
					m -= uint32_t(1) << (BUCKET_SIZE - 1 - __builtin_clz(m));
				}
				m |= uint32_t(1) << (i & (BUCKET_SIZE - 1));
				range_mask[i] = m;
			} else {
				range_mask[i] = 1;
			}
		}
		for (int i = 0; i < n; i++) {
			pref_data[i] = data[i];
			if (i & (BUCKET_SIZE-1)) {
				setmin(pref_data[i], pref_data[i-1]);
			}
		}
		for (int i = n-1; i >= 0; i--) {
			suff_data[i] = data[i];
			if (i+1 < n && ((i+1) & (BUCKET_SIZE-1))) {
				setmin(suff_data[i], suff_data[i+1]);
			}
		}
		for (int i = 0; i < num_buckets(); i++) {
			sparse_table[i] = data[i * BUCKET_SIZE];
			for (int v = 1; v < BUCKET_SIZE; v++) {
				setmin(sparse_table[i], data[i * BUCKET_SIZE + v]);
			}
		}
		for (int l = 0; l+1 < num_levels(); l++) {
			for (int i = 0; i + (1 << (l+1)) <= num_buckets(); i++) {
				sparse_table[(l+1) * num_buckets() + i] = min(sparse_table[l * num_buckets() + i], sparse_table[l * num_buckets() + i + (1 << l)]);
			}
		}
	}

	T query(int l, int r) const {
		assert(l <= r);
		int bucket_l = (l >> BUCKET_SIZE_LOG);
		int bucket_r = (r >> BUCKET_SIZE_LOG);
		if (bucket_l == bucket_r) {
			uint32_t msk = range_mask[r] & ~((uint32_t(1) << (l & (BUCKET_SIZE-1))) - 1);
			int ind = (l & ~(BUCKET_SIZE-1)) + __builtin_ctz(msk);
			return data[ind];
		} else {
			T ans = min(suff_data[l], pref_data[r]);
			bucket_l++;
			if (bucket_l < bucket_r) {
				int level = (32 - __builtin_clz(bucket_r - bucket_l)) - 1;
				setmin(ans, sparse_table[level * num_buckets() + bucket_l]);
				setmin(ans, sparse_table[level * num_buckets() + bucket_r - (1 << level)]);
			}
			return ans;
		}
	}
};

template <typename T> using RangeMaxQuery = RangeMinQuery<T, std::greater<T>>;
#line 7 "verify/staticrmq.test.cpp"

int main() {
	std::ios_base::sync_with_stdio(false), std::cin.tie(nullptr);

	int N, Q; std::cin >> N >> Q;
	std::vector<int> A(N); for (auto& x : A) std::cin >> x;
	RangeMinQuery<int> rmq(A);
	for (int q = 0; q < Q; q++) {
		int l, r; std::cin >> l >> r;
		std::cout << rmq.query(l, r-1) << '\n';
	}

	return 0;
}

// clang-format off
// @formatter:off
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpragmas"
#pragma GCC diagnostic ignored "-Wunknown-warning-option"
#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#pragma GCC diagnostic ignored "-Wmultistatement-macros"
#include <bits/stdc++.h>
// src/rmq.hpp
template<typename T,class Compare=std::less<T>>class RangeMinQuery:private Compare{
static const int BUCKET_SIZE=32;
static const int BUCKET_SIZE_LOG=5;
static_assert(BUCKET_SIZE==(1<<BUCKET_SIZE_LOG),"BUCKET_SIZE should be a power of 2");
static const int CACHE_LINE_ALIGNMENT=64;
int n=0;
std::vector<T>data;
std::vector<T>pref_data;
std::vector<T>suff_data;
std::vector<T>sparse_table;
std::vector<uint32_t>range_mask;
private:
int num_buckets()const{
return n>>BUCKET_SIZE_LOG;
}
int num_levels()const{
return num_buckets()?32-__builtin_clz(num_buckets()):0;
}
int sparse_table_size()const{
return num_buckets()*num_levels();
}
private:
const T&min(const T&a,const T&b)const{
return Compare::operator()(a,b)?a:b;
}
void setmin(T&a,const T&b)const{
if(Compare::operator()(b,a))a=b;
}
template<typename Vec>static int get_size(const Vec&v){using std::size;return int(size(v));}
public:
RangeMinQuery(){}
template<typename Vec>explicit RangeMinQuery(const Vec&data_,const Compare&comp_=Compare())
:Compare(comp_)
,n(get_size(data_))
,data(n)
,pref_data(n)
,suff_data(n)
,sparse_table(sparse_table_size())
,range_mask(n)
{
for(int i=0;i<n;i++)data[i]=data_[i];
for(int i=0;i<n;i++){
if(i&(BUCKET_SIZE-1)){
uint32_t m=range_mask[i-1];
while(m&&!Compare::operator()(data[(i|(BUCKET_SIZE-1))-__builtin_clz(m)],data[i])){
m-=uint32_t(1)<<(BUCKET_SIZE-1-__builtin_clz(m));
}
m|=uint32_t(1)<<(i&(BUCKET_SIZE-1));
range_mask[i]=m;
}else{
range_mask[i]=1;
}
}
for(int i=0;i<n;i++){
pref_data[i]=data[i];
if(i&(BUCKET_SIZE-1)){
setmin(pref_data[i],pref_data[i-1]);
}
}
for(int i=n-1;i>=0;i--){
suff_data[i]=data[i];
if(i+1<n&&((i+1)&(BUCKET_SIZE-1))){
setmin(suff_data[i],suff_data[i+1]);
}
}
for(int i=0;i<num_buckets();i++){
sparse_table[i]=data[i*BUCKET_SIZE];
for(int v=1;v<BUCKET_SIZE;v++){
setmin(sparse_table[i],data[i*BUCKET_SIZE+v]);
}
}
for(int l=0;l+1<num_levels();l++){
for(int i=0;i+(1<<(l+1))<=num_buckets();i++){
sparse_table[(l+1)*num_buckets()+i]=min(sparse_table[l*num_buckets()+i],sparse_table[l*num_buckets()+i+(1<<l)]);
}
}
}
T query(int l,int r)const{
assert(l<=r);
int bucket_l=(l>>BUCKET_SIZE_LOG);
int bucket_r=(r>>BUCKET_SIZE_LOG);
if(bucket_l==bucket_r){
uint32_t msk=range_mask[r]&~((uint32_t(1)<<(l&(BUCKET_SIZE-1)))-1);
int ind=(l&~(BUCKET_SIZE-1))+__builtin_ctz(msk);
return data[ind];
}else{
T ans=min(suff_data[l],pref_data[r]);
bucket_l++;
if(bucket_l<bucket_r){
int level=(32-__builtin_clz(bucket_r-bucket_l))-1;
setmin(ans,sparse_table[level*num_buckets()+bucket_l]);
setmin(ans,sparse_table[level*num_buckets()+bucket_r-(1<<level)]);
}
return ans;
}
}
};
template<typename T>using RangeMaxQuery=RangeMinQuery<T,std::greater<T>>;
// verify/staticrmq.test.cpp
int main(){
std::ios_base::sync_with_stdio(false),std::cin.tie(nullptr);
int N,Q;std::cin>>N>>Q;
std::vector<int>A(N);for(auto&x:A)std::cin>>x;
RangeMinQuery<int>rmq(A);
for(int q=0;q<Q;q++){
int l,r;std::cin>>l>>r;
std::cout<<rmq.query(l,r-1)<<'\n';
}
return 0;
}
#pragma GCC diagnostic pop
// clang-format on
// @formatter:on

Test cases

Env	Name	Status	Elapsed	Memory
g++-sanitizer	example_00	AC	15 ms	8 MB
g++-sanitizer	max_random_00	AC	201 ms	23 MB
g++-sanitizer	max_random_01	AC	190 ms	23 MB
g++-sanitizer	max_random_02	AC	186 ms	24 MB
g++-sanitizer	max_random_03	AC	190 ms	23 MB
g++-sanitizer	max_random_04	AC	185 ms	24 MB
g++-sanitizer	random_00	AC	168 ms	21 MB
g++-sanitizer	random_01	AC	167 ms	23 MB
g++-sanitizer	random_02	AC	110 ms	13 MB
g++-sanitizer	random_03	AC	65 ms	22 MB
g++-sanitizer	random_04	AC	96 ms	18 MB
g++-sanitizer	small_00	AC	17 ms	8 MB
g++-sanitizer	small_01	AC	18 ms	8 MB
g++-sanitizer	small_02	AC	18 ms	8 MB
g++-sanitizer	small_03	AC	12 ms	8 MB
g++-sanitizer	small_04	AC	16 ms	8 MB
g++-sanitizer	small_05	AC	15 ms	8 MB
g++-sanitizer	small_06	AC	13 ms	8 MB
g++-sanitizer	small_07	AC	14 ms	8 MB
g++-sanitizer	small_08	AC	17 ms	8 MB
g++-sanitizer	small_09	AC	17 ms	8 MB
g++-sanitizer	small_values_00	AC	205 ms	24 MB
g++-sanitizer	small_width_query_00	AC	245 ms	23 MB
g++-sanitizer	small_width_query_01	AC	246 ms	23 MB
g++-sanitizer	small_width_query_02	AC	241 ms	23 MB
g++-sanitizer	small_width_query_03	AC	236 ms	23 MB
g++-sanitizer	small_width_query_04	AC	200 ms	24 MB
g++	example_00	AC	3 ms	4 MB
g++	max_random_00	AC	127 ms	14 MB
g++	max_random_01	AC	124 ms	14 MB
g++	max_random_02	AC	126 ms	14 MB
g++	max_random_03	AC	128 ms	14 MB
g++	max_random_04	AC	125 ms	14 MB
g++	random_00	AC	103 ms	12 MB
g++	random_01	AC	107 ms	13 MB
g++	random_02	AC	66 ms	5 MB
g++	random_03	AC	41 ms	13 MB
g++	random_04	AC	41 ms	9 MB
g++	small_00	AC	3 ms	4 MB
g++	small_01	AC	2 ms	4 MB
g++	small_02	AC	2 ms	4 MB
g++	small_03	AC	2 ms	4 MB
g++	small_04	AC	2 ms	4 MB
g++	small_05	AC	2 ms	4 MB
g++	small_06	AC	2 ms	4 MB
g++	small_07	AC	2 ms	4 MB
g++	small_08	AC	2 ms	4 MB
g++	small_09	AC	2 ms	4 MB
g++	small_values_00	AC	113 ms	14 MB
g++	small_width_query_00	AC	143 ms	14 MB
g++	small_width_query_01	AC	147 ms	14 MB
g++	small_width_query_02	AC	136 ms	14 MB
g++	small_width_query_03	AC	141 ms	14 MB
g++	small_width_query_04	AC	132 ms	14 MB

Back to top page