RT

代码：

#include <bits/stdc++.h>
#define N 1000001
#define M 20
using namespace std;
int n, m, l, r, a[N], lo[N], dp[N][M];
inline int read() {
    int f = 0, n = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') n = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        f = (f << 1) + (f << 3) + ch - '0';
        ch = getchar();
    }
    return f * n;
}
signed main() {
    n = read(), m = read();
    for (int i = 2; i <= n; ++ i) 
        lo[i] = lo[i >> 1] + 1;
    for (int i = 1; i <= n; ++ i) {
        a[i] = read();
        dp[i][0] = a[i];
    }
    int x = lo[n];
    for (int j = 1; j <= x; ++ j) {
        for (int i = 1; i <= n - (1 << (j - 1)) + 1; ++ i) 
            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
    }
    while (m --) {
        l = read(), r = read();
        int x = lo[r - l + 1];
        cout << max(dp[l][x], dp[r - (1 << x) + 1][x]) << endl;
    }
    return 0;
}

记录