tests/sparse_table.test.cpp

View this file on GitHub
Last update: 2024-02-01 17:09:56-05:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include "../content/data_structures/sparse_table.h"

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, q;
	cin>>n>>q;
	vector<int> v(n);
	for(auto &i: v)
		cin>>i;
	
	sparse_table<int> sp;
	sp.build(v, [](int x, int y){ return min(x, y);});
	
	while(q--){
		int l, r;
		cin>>l>>r;
		cout<<sp.query(l, r-1)<<'\n';
	}
}

#line 1 "tests/sparse_table.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#line 1 "content/utils/template.h"
/**
 * @brief My starter code
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end());

#ifdef LOCAL
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args> void pr(Args... args){}
#endif

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#line 3 "content/data_structures/sparse_table.h"

/**
 * @brief Sparse Table
 * @docs docs/sparse_table.md
 */

template<class T> struct sparse_table{
	
	int n; vector<vector<T>> sp;
	function<T(T, T)> merge;
	
	T query(int l, int r){
		int k = __lg(r-l+1);
		return merge(sp[k][l], sp[k][r-(1<<k)+1]);
	}
	void build(vector<T> v, function<T(T, T)> f){
		merge = f;
		n = (int)size(v);
		sp.resize(__lg(n)+1);
		sp[0] = v;
		for(int i = 1; i <= __lg(n); i++){
			sp[i].resize(n);
			for(int j = 0; j+(1<<i)-1 < n; j++){
				sp[i][j] = merge(sp[i-1][j], sp[i-1][j+(1<<(i-1))]);
			}
		}
	}
};
#line 3 "tests/sparse_table.test.cpp"

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, q;
	cin>>n>>q;
	vector<int> v(n);
	for(auto &i: v)
		cin>>i;
	
	sparse_table<int> sp;
	sp.build(v, [](int x, int y){ return min(x, y);});
	
	while(q--){
		int l, r;
		cin>>l>>r;
		cout<<sp.query(l, r-1)<<'\n';
	}
}