test/library_checker/data_structure/staticrmq_2.test.cpp

View this file on GitHub
Last update: 2022-08-24 04:05:14+09:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

スパーステーブル (data_structure/sequence/sparse_table.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
#include "../../../data_structure/sequence/sparse_table.hpp"
int main(){
  int N, Q;
  cin >> N >> Q;
  vector<int> a(N);
  for (int i = 0; i < N; i++){
    cin >> a[i];
  }
  sparse_table<int> ST(a, [](int a, int b){return min(a, b);}, INF);
  for (int i = 0; i < Q; i++){
    int l, r;
    cin >> l >> r;
    cout << ST.query(l, r) << endl;
  }
}

#line 1 "test/library_checker/data_structure/staticrmq_2.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
#line 2 "data_structure/sequence/sparse_table.hpp"
/**
 * @brief スパーステーブル
*/
template <typename T>
struct sparse_table{
  vector<vector<T>> ST;
  function<T(T, T)> f;
  T E;
  sparse_table(){
  }
  sparse_table(int N, function<T(T, T)> f, T E): f(f), E(E){
    int LOG = 32 - __builtin_clz(N);
    ST = vector<vector<T>>(LOG, vector<T>(N, E));
  }
  sparse_table(vector<T> &A, function<T(T, T)> f, T E): f(f), E(E){
    int N = A.size();
    int LOG = 32 - __builtin_clz(N);
    ST = vector<vector<T>>(LOG, vector<T>(N));
    for (int i = 0; i < N; i++){
      ST[0][i] = A[i];
    }
    for (int i = 0; i < LOG - 1; i++){
      for (int j = 0; j < N - (1 << i); j++){
        ST[i + 1][j] = f(ST[i][j], ST[i][j + (1 << i)]);
      }
    }
  }
  int query(int L, int R){
    if (L == R){
      return E;
    }
    int d = 31 - __builtin_clz(R - L);
    return f(ST[d][L], ST[d][R - (1 << d)]);
  }
};
#line 6 "test/library_checker/data_structure/staticrmq_2.test.cpp"
int main(){
  int N, Q;
  cin >> N >> Q;
  vector<int> a(N);
  for (int i = 0; i < N; i++){
    cin >> a[i];
  }
  sparse_table<int> ST(a, [](int a, int b){return min(a, b);}, INF);
  for (int i = 0; i < Q; i++){
    int l, r;
    cin >> l >> r;
    cout << ST.query(l, r) << endl;
  }
}