Rmq

template <typename T, typename Cmp = std::less<T>>
struct Rmq {
  constexpr static int B = 64;
  using uint64 = unsigned long long;
  int n;
  std::vector<std::vector<T>> mat;
  std::vector<T> pref;
  std::vector<T> suff;
  std::vector<T> a;
  std::vector<uint64> avail;
  Cmp cmp;

  Rmq(const std::vector<T>& _a, Cmp&& _cmp = Cmp {}) : n(int(_a.size())), pref(_a), suff(_a), a(_a), cmp(_cmp) {
    for (int i = 1; i < n; ++i) {
      if (i % B != 0) {
        pref[i] = std::min(pref[i - 1], pref[i], cmp);
      }
    }
    for (int i = n - 2; i >= 0; --i) {
      if (i % B != B - 1) {
        suff[i] = std::min(suff[i], suff[i + 1], cmp);
      }
    }
    int m = n / B;
    int max_log = (m == 0 ? 0 : 31 ^ __builtin_clz(m));
    mat.assign(max_log + 1, std::vector<T>(m));
    for (int i = 0; i < m; ++i) {
      mat[0][i] = suff[i * B];
    }
    for (int lg = 0; lg < max_log; ++lg) {
      for (int i = 0; i <= m - (2 << lg); ++i) {
        mat[lg + 1][i] = std::min(mat[lg][i], mat[lg][i + (1 << lg)], cmp);
      }
    }
    avail.resize(n);
    for (int l = 0; l < n; l += B) {
      int r = std::min(l + B, n);
      uint64 stk = 0;
      for (int bit = 0; bit < r - l; ++bit) {
        while (stk != 0) {
          int top = 63 ^ __builtin_clzll(stk);
          if (cmp(a[l + top], a[l + bit])) {
            break;
          } else {
            stk ^= uint64(1) << top;
          }
        }
        stk ^= uint64(1) << bit;
        avail[l + bit] = stk;
      }
    }
  }

  [[nodiscard]] T get(int l, int r) const {
    assert(0 <= l && l < r && r <= n);
    if (l / B != (r - 1) / B) {
      T res = std::min(suff[l], pref[r - 1], cmp);
      l = l / B + 1;
      r = (r - 1) / B;
      if (l < r) {
        int max_log = 31 ^ __builtin_clz(r - l);
        res = std::min(res, std::min(mat[max_log][l], mat[max_log][r - (1 << max_log)], cmp), cmp);
      }
      return res;
    } else {
      return a[l + __builtin_ctzll(avail[r - 1] >> (l % B))];
    }
  }
};