lmori's Library
This documentation is automatically generated by competitive-verifier/competitive-verifier
verify/LibraryChecker/data-structure/others/StaticRMQ_SqrtTree.test.cpp
- View this file on GitHub
- Last update: 2025-09-28 00:58:56+09:00
- Problem: https://judge.yosupo.jp/problem/staticrmq
Depends on
Code
#include "../../../../template/template.hpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#include "../../../../data-structure/others/SqrtTree.hpp"
using S = int;
S op(S a, S b) {
return min(a, b);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
in(n, q);
vector<int> a(n);
in(a);
SqrtTree<S, op> t(a);
rep(i, q) {
int l, r;
in(l, r);
out(t.prod(l, r));
}
}#line 2 "template/template.hpp"
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using ull = unsigned long long;
using ld = long double;
using int128 = __int128_t;
#define all(x) (x).begin(), (x).end()
#define uniqv(v) v.erase(unique(all(v)), v.end())
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define REP1(i, n) for (auto i = std::decay_t<decltype(n)>{}; (i) != (n); ++(i))
#define REP2(i, l, r) for (auto i = (l); (i) != (r); ++(i))
#define rep(...) OVERLOAD_REP(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define logfixed(x) cout << fixed << setprecision(10) << x << endl;
ostream &operator<<(ostream &dest, __int128_t value) {
ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(ios_base::badbit);
}
}
return dest;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 != (int)v.size() ? " " : "");
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &set_var) {
for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
os << *itr;
++itr;
if (itr != set_var.end()) os << " ";
itr--;
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &set_var) {
for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
os << *itr;
++itr;
if (itr != set_var.end()) os << " ";
itr--;
}
return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &map_var) {
for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
os << itr->first << " -> " << itr->second << "\n";
}
return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const unordered_map<T, U> &map_var) {
for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
os << itr->first << " -> " << itr->second << "\n";
}
return os;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pair_var) {
os << pair_var.first << " " << pair_var.second;
return os;
}
void out() { cout << '\n'; }
template <class T, class... Ts>
void out(const T &a, const Ts &...b) {
cout << a;
(cout << ... << (cout << ' ', b));
cout << '\n';
}
void outf() { cout << '\n'; }
template <class T, class... Ts>
void outf(const T &a, const Ts &...b) {
cout << fixed << setprecision(14) << a;
(cout << ... << (cout << ' ', b));
cout << '\n';
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &in : v) is >> in;
return is;
}
inline void in(void) { return; }
template <typename First, typename... Rest>
void in(First &first, Rest &...rest) {
cin >> first;
in(rest...);
return;
}
template <typename T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <typename T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
vector<lint> dx8 = {1, 1, 0, -1, -1, -1, 0, 1};
vector<lint> dy8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<lint> dx4 = {1, 0, -1, 0};
vector<lint> dy4 = {0, 1, 0, -1};
#pragma endregion
#line 2 "verify/LibraryChecker/data-structure/others/StaticRMQ_SqrtTree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/staticrmq"
#line 1 "data-structure/others/SqrtTree.hpp"
template <class S, auto op>
class SqrtTree {
private:
int n, lg, indexSz;
vector<S> v;
vector<int> clz, layers, onLayer;
vector<vector<S>> prefix, suffix, between;
void build(int layer, int lBound, int rBound, int betweenOffs) {
if (layer >= (int)layers.size()) {
return;
}
int bSz = 1 << ((layers[layer] + 1) >> 1);
for (int l = lBound; l < rBound; l += bSz) {
int r = min(l + bSz, rBound);
prefix[layer][l] = v[l];
for (int i = l + 1; i < r; i++) {
prefix[layer][i] = op(prefix[layer][i - 1], v[i]);
}
suffix[layer][r - 1] = v[r - 1];
for (int i = r - 2; i >= l; i--) {
suffix[layer][i] = op(v[i], suffix[layer][i + 1]);
}
build(layer + 1, l, r, betweenOffs);
}
if (layer == 0) {
int bSzLog = (lg + 1) >> 1;
for (int i = 0; i < indexSz; i++) {
v[n + i] = suffix[0][i << bSzLog];
}
build(1, n, n + indexSz, (1 << lg) - n);
} else {
int bSzLog = (layers[layer] + 1) >> 1;
int bCntLog = layers[layer] >> 1;
int bSz = 1 << bSzLog;
int bCnt = (rBound - lBound + bSz - 1) >> bSzLog;
for (int i = 0; i < bCnt; i++) {
S ans;
for (int j = i; j < bCnt; j++) {
S add = suffix[layer][lBound + (j << bSzLog)];
ans = (i == j) ? add : op(ans, add);
between[layer - 1][betweenOffs + lBound + (i << bCntLog) + j] = ans;
}
}
}
}
inline S query(int l, int r, int betweenOffs, int base) {
if (l == r) {
return v[l];
}
if (l + 1 == r) {
return op(v[l], v[r]);
}
int layer = onLayer[clz[(l - base) ^ (r - base)]];
int bSzLog = (layers[layer] + 1) >> 1;
int bCntLog = layers[layer] >> 1;
int lBound = (((l - base) >> layers[layer]) << layers[layer]) + base;
int lBlock = ((l - lBound) >> bSzLog) + 1;
int rBlock = ((r - lBound) >> bSzLog) - 1;
S ans = suffix[layer][l];
if (lBlock <= rBlock) {
S add = (layer == 0) ? (
query(n + lBlock, n + rBlock, (1 << lg) - n, n))
: (
between[layer - 1][betweenOffs + lBound + (lBlock << bCntLog) + rBlock]);
ans = op(ans, add);
}
ans = op(ans, prefix[layer][r]);
return ans;
}
public:
inline S prod(int l, int r) {
return query(l, r - 1, 0, 0);
}
SqrtTree() {}
SqrtTree(const vector<S> a)
: n((int)a.size()), v(a) {
lg = 0;
while ((1 << lg) < n) lg++;
clz.assign(1 << lg, 0);
onLayer.assign(lg + 1, 0);
clz[0] = 0;
for (int i = 1; i < (int)clz.size(); i++) {
clz[i] = clz[i >> 1] + 1;
}
int tlg = lg;
while (tlg > 1) {
onLayer[tlg] = (int)layers.size();
layers.push_back(tlg);
tlg = (tlg + 1) >> 1;
}
for (int i = lg - 1; i >= 0; i--) {
onLayer[i] = max(onLayer[i], onLayer[i + 1]);
}
int betweenLayers = max(0, (int)layers.size() - 1);
int bSzLog = (lg + 1) >> 1;
int bSz = 1 << bSzLog;
indexSz = (n + bSz - 1) >> bSzLog;
v.resize(n + indexSz);
prefix.assign(layers.size(), vector<S>(n + indexSz));
suffix.assign(layers.size(), vector<S>(n + indexSz));
between.assign(betweenLayers, vector<S>((1 << lg) + bSz));
build(0, 0, n, 0);
}
};
#line 4 "verify/LibraryChecker/data-structure/others/StaticRMQ_SqrtTree.test.cpp"
using S = int;
S op(S a, S b) {
return min(a, b);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
in(n, q);
vector<int> a(n);
in(a);
SqrtTree<S, op> t(a);
rep(i, q) {
int l, r;
in(l, r);
out(t.prod(l, r));
}
}