RMQ infoarena

#include <bits/stdc++.h>
#define maxn 100000
#define logmaxn 17

using namespace std;

ifstream fin ("rmq.in");
ofstream fout ("rmq.out");

int n, Q, x, y, k, v[maxn + 1], lg[maxn + 1], M[maxn + 1][logmaxn + 1];

int main () {
    fin >> n >> Q;
    for (int i = 0; i < n; i ++) {
        fin >> v[i];
        M[i][0] = i;
    }
    lg[1] = 0;
    for (int i = 2; i <= n; i ++) lg[i] = lg[i / 2] + 1;
    for (int j = 1; (1 << j) <= n; j ++)
    for (int i = 0; i + (1 << j) - 1 < n; i ++)
    if (v[M[i][j - 1]] < v[M[i + (1 << (j - 1))][j - 1]]) M[i][j] = M[i][j - 1];
    else M[i][j] = M[i + (1 << (j - 1))][j - 1];
    while (Q --) {
        fin >> x >> y;
        x --, y --;
        k = lg[y - x + 1];
        if (v[M[x][k]] <= v[M[y - (1 << k) + 1][k]]) fout << v[M[x][k]] << '\n';
        else fout << v[M[y - (1 << k) + 1][k]] << '\n';
    }
    fin.close ();
    fout.close ();
    return 0;
}