RMQ normal

vector<int> a, lg2;
vector<vector<int>> rmq_min, rmq_max;

void compute_lg2() {
    lg2 = vector<int>(N + 1);
    lg2[1] = 0;
    for(int i = 2; i <= N; ++i)
        lg2[i] = lg2[i >> 1] + 1;
}

void compute_rmq() {
    rmq_min = vector<vector<int>>(N + 1, vector<int>((int)log2(N) + 1, INF));
    rmq_max = vector<vector<int>>(N + 1, vector<int>((int)log2(N) + 1));
    for(int i = 1; i <= N; ++i)
        rmq_min[i][0] = rmq_max[i][0] = a[i];
    for(int j = 1; (1 << j) <= N; ++j)
        for(int i = 1; i + (1 << j) - 1 <= N; ++i) {
            rmq_min[i][j] = min(rmq_min[i][j - 1], rmq_min[i + (1 << (j - 1))][j - 1]);
            rmq_max[i][j] = max(rmq_max[i][j - 1], rmq_max[i + (1 << (j - 1))][j - 1]);
        }
}

int query_min(int l, int r) {
    int k = lg2[r - l + 1];
    int dif = (r - l + 1) - (1 << k);
    return min(rmq_min[l][k], rmq_min[l + dif][k]);
}

int query_max(int l, int r) {
    int k = lg2[r - l + 1];
    int dif = (r - l + 1) - (1 << k);
    return max(rmq_max[l][k], rmq_max[l + dif][k]);
}

// in main() trebuie apelate compute_lg2() si compute_rmq()!!!!