DisjointSparseTable

template <typename T, typename F>
struct DisjointSparseTable {
  int n;
  std::vector<std::vector<T>> mat;
  F func;

  DisjointSparseTable(const std::vector<T>& a, const F& f = F {}) : n(int(a.size())), func(f) {
    mat.push_back(a);
    for (int p = 1; (1 << p) < n; ++p) {
      mat.emplace_back(n);
      for (int mid = 1 << p; mid < n; mid += 1 << (p + 1)) {
        mat[p][mid - 1] = a[mid - 1];
        for (int j = mid - 2; j >= (mid ^ 1 << p); --j) {
          mat[p][j] = func(a[j], mat[p][j + 1]);
        }
        mat[p][mid] = a[mid];
        for (int j = mid + 1; j < std::min(n, mid + (1 << p)); ++j) {
          mat[p][j] = func(mat[p][j - 1], a[j]);
        }
      }
    }
  }

  [[nodiscard]] T get(int l, int r) const {
    assert(0 <= l && l < r && r <= n);
    if (r - l == 1) {
      return mat[0][l];
    }
    int p = 31 ^ __builtin_clz(l ^ (r - 1));
    return func(mat[p][l], mat[p][r - 1]);
  }
};