分块太好用辣

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define ULL unsigned long long
#define all(v) v.begin(), v.end()
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
constexpr int N =  1 * 1e6 + 10,M = 5 * 1e3 + 10,inf = 0x3f3f3f3f;

int n,m;
int id[N],a[N],b[N],len,s[N];
int query(int l,int r)
{
    int sid = id[l] , eid = id[r];
    int res = -inf;
    if(sid == eid)
    {
        for(int i=l;i<=r;i++) res = max(res,a[i]);
        return res;
    }

    for(int i=l;id[i]==sid;i++) res = max(res,a[i]);
    for(int i=sid+1;i<eid;i++) res = max(res,s[i]);
    for(int i=r;id[i]==eid;i--) res = max(res,a[i]);
    return res;
}
void solve()
{
    cin >> n >> m;
    len = sqrt(n);
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        id[i] = (i-1) / len + 1;
        s[id[i]]  = max(a[i],s[id[i]]);
    }

    while (m--)
    {
        int l,r;
        cin >> l >> r;
        cout << query(l,r) << '\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(nullptr),cout.tie(nullptr);
    int _=1;
    // cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

/**
 *    author: Nijika_jia
 *    created: 2024.10.28 13:08:13
 */