暴力

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n, m;
int a[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        int ans = a[l];
        for (int i = l + 1; i <= r; i++)
            ans = max(ans, a[i]);
        cout << ans << "\n";
    }
    return 0;
}

预处理每个位置开始 $\sqrt{n}$ 个元素的最值

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int LEN = 333;
int n, m;
int a[MAXN + 5];
// b[i] 记录 a[i] 开始的 LEN 个元素的最值
int b[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        b[i] = a[i];
        for (int j = i + 1; j <= n && j <= i + LEN - 1; j++)
            b[i] = max(b[i], a[j]);
    }
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        int ans = a[l];
        while (l + LEN - 1 <= r)
        {
            ans = max(ans, b[l]);
            l += LEN;
        }
        while (l <= r)
        {
            ans = max(ans, a[l]);
            l++;
        }
        cout << ans << "\n";
    }
    return 0;
}

st 表

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int n, m;
int a[MAXN + 5];
// st[i][j] a[i] 开始的 2^j 个元素的最值
int st[MAXN][20];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int j = 0; j <= 20; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            if (j == 0)
                st[i][j] = a[i];
            else
                st[i][j] = max(st[i][j - 1],
                               st[i + (1 << (j - 1))][j - 1]);
        }
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        int len = (r - l + 1);
        int j = log2(len);
        cout << max(st[l][j], st[r - (1 << j) + 1][j]) << "\n";
    }
    return 0;
}