data-structure/test/Static_RMQ.test.cpp

View this file on GitHub
Last update: 2023-07-25 00:50:50+07:00
Problem: https://judge.yosupo.jp/problem/staticrmq

Depends on

Range Minimum/Maximum Query (Sparse Table) (data-structure/rmq.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include <bits/stdc++.h>

using namespace std;

#include "../rmq.hpp"

signed main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (auto &x : a) cin >> x;
  rmq<int, range_min> st(a);
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << st.get(l, r) << '\n';
  }
}

#line 1 "data-structure/test/Static_RMQ.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"

#include <bits/stdc++.h>

using namespace std;

#line 1 "data-structure/rmq.hpp"
// RMQ using Sparse Table
// range_min for min, range_max for max

template <class T, T (*op)(T, T)>
struct rmq {
  rmq() = default;
  rmq(const vector<T>& v) : t{v}, n{(int)v.size()} {
    for (int k = 1; (1 << k) <= n; ++k) {
      t.emplace_back(n - (1 << k) + 1);
      for (int i = 0; i + (1 << k) <= n; ++i) {
        t[k][i] = op(t[k - 1][i], t[k - 1][i + (1 << (k - 1))]);
      }
    }
  }

  // get range [l, r-1]
  // doesn't work for empty range
  T get(int l, int r) const {
    assert(0 <= l && l < r && r <= n);
    int k = __lg(r - l);
    return op(t[k][l], t[k][r - (1 << k)]);
  }

 private:
  vector<vector<T>> t;
  int n;
};

template <class T>
T range_min(T a, T b) {
  return b < a ? b : a;
}
template <class T>
T range_max(T a, T b) {
  return a < b ? b : a;
}
#line 8 "data-structure/test/Static_RMQ.test.cpp"

signed main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (auto &x : a) cin >> x;
  rmq<int, range_min> st(a);
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << st.get(l, r) << '\n';
  }
}