A0687 ST表1

#include <bits/stdc++.h>
using namespace std;

class FastIO {
    static const int S = 1 << 16;
    char buf[S];
    int pos = 0, len = 0;
    char out[S];
    int opos = 0;

    inline char getChar() {
        if (pos == len) {
            len = (int)fread(buf, 1, S, stdin);
            pos = 0;
            if (len == 0) return 0;
        }
        return buf[pos++];
    }

public:
    inline int readInt() {
        char c = getChar();
        while (c && (c < '0' || c > '9') && c != '-') c = getChar();
        int sign = 1;
        if (c == '-') {
            sign = -1;
            c = getChar();
        }
        int x = 0;
        while (c >= '0' && c <= '9') {
            x = x * 10 + (c - '0');
            c = getChar();
        }
        return x * sign;
    }

    inline void writeInt(int x) {
        if (x == 0) {
            putChar('0');
        } else {
            if (x < 0) {
                putChar('-');
                x = -x;
            }
            char tmp[16];
            int n = 0;
            while (x) {
                tmp[n++] = (char)('0' + x % 10);
                x /= 10;
            }
            while (n) putChar(tmp[--n]);
        }
        putChar('\n');
    }

    inline void putChar(char c) {
        if (opos == S) flush();
        out[opos++] = c;
    }

    void flush() {
        if (opos) {
            fwrite(out, 1, opos, stdout);
            opos = 0;
        }
    }
};

int main() {
    FastIO io;

    int N = io.readInt();
    int M = io.readInt();

    vector<int> a(N + 1);
    for (int i = 1; i <= N; i++) a[i] = io.readInt();

    // lg[i] = floor(log2(i))
    vector<int> lg(N + 2, 0);
    for (int i = 2; i <= N + 1; i++) lg[i] = lg[i >> 1] + 1;

    // st[k][i]：从 i 开始、长度为 2^k 的区间最大值
    int K = lg[N] + 1;
    vector<vector<int>> st(K, vector<int>(N + 2, 0));
    for (int i = 1; i <= N; i++) st[0][i] = a[i];
    for (int k = 1; k < K; k++) {
        int len = 1 << k, half = len >> 1;
        for (int i = 1; i + len - 1 <= N; i++) {
            st[k][i] = max(st[k - 1][i], st[k - 1][i + half]);
        }
    }

    for (int q = 0; q < M; q++) {
        int l = io.readInt();
        int r = io.readInt();
        int k = lg[r - l + 1];
        int ans = max(st[k][l], st[k][r - (1 << k) + 1]);
        io.writeInt(ans);
    }
    io.flush();
    return 0;
}