rmq板子

typedef long long LL;
constexpr inline int lg2(LL x) { return sizeof(LL) * 8 - 1 - __builtin_clzll(x); }

template<typename T, size_t N, size_t K>
struct RangeQuery {
T mx[N][K], mn[N][K];
RangeQuery(const vector& a) {
int n = a.size();
for (int i = 0; i < n; ++i) {
mx[i][0] = mn[i][0] = a[i];
}
for (int k = 1; k < K; ++k) {
for (int i = 0; i + (1 << k) <= n; ++i) {
int j = i + (1 << (k - 1));
mx[i][k] = max(mx[i][k - 1], mx[j][k - 1]);
mn[i][k] = min(mn[i][k - 1], mn[j][k - 1]);
}
}
}
T get_min(int x, int y) {
int k = lg2(y - x + 1);
return min(mn[x][k], mn[y - (1 << k) + 1][k]);
}
T get_max(int x, int y) {
if (y < x) return 0;
int k = lg2(y - x + 1);
return max(mx[x][k], mx[y - (1 << k) + 1][k]);
}
};

const int N = 1e5 + 10;
const int K = 20;
using rmq = RangeQuery<int, N, K>;