解题思路是把数据分块，总共分成s块，查询复杂度为O(n/s+s)。最后结果不是TLE居然WA了。

#include <algorithm>
#include <bits/stdc++.h>
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}

int N, M, l, r;
int a[100005];

int main()
{
    N = read(), M = read();
    int c[1005] = {0};
    // 分为s块
    int s = floor(sqrt(N));
    //每个块的个数
    int num = N / s;
    //剩下几个元素组成一个块
    int res = N - s * num;
    int cnt = 1;
    for (int i = 0; i < s; ++i)
    {
        int maxn = -1;
        for (int j = 0; j < num; ++j)
        {
            a[cnt] = read();
            maxn = max(maxn, a[cnt]);
            ++cnt;
        }
        c[i] = maxn;
    }
    for (; res > 0; --res)
    {
        a[cnt++] = read();
    }
    // for(int i=0;i<s;i++){
    //     printf("%d\n",c[i]);
    // }
    getchar();
    for (int i = 0; i < M; ++i)
    {
        l = read(), r = read();
        int start = l / num, end = r / num;
        int lmaxn = -1, rmaxn = -1, result = -1;
        int flag1 = 0;
        // 处理左边多出来的
        if (l != (start * num + 1))
        {
            flag1 = 1;
            for (int j = l; j <= (start + 1) * num; ++j)
            {
                lmaxn = max(lmaxn, a[j]);
            }
        }
        //处理右边多出来的
        if (r != end * num)
        {
            for (int j = end * num + 1; j <= r; ++j)
            {
                rmaxn = max(rmaxn, a[j]);
            }
        }
        for (int j = start + flag1; j < end; ++j)
        {
            result = max(result, c[j]);
        }
        result = max3(lmaxn, rmaxn, result);
        printf("%d\n", result);
    }
    return 0;
}