【模板】静态区间最值

#include <bits/stdc++.h>
#define pii pair<int, int>
#define endl '\n'
using namespace std;

const int inf = 1e9+7;
const int mxa = 5e5+10;
const int mxb = 750;

int a[mxa];
int brange_mx[mxb][mxb];
int brange_mn[mxb][mxb];
int bpre_mx[mxb][mxb];
int bpre_mn[mxb][mxb];
int bsuf_mx[mxb][mxb];
int bsuf_mn[mxb][mxb];

int get(int x, int blen) {
    return (x-1)/blen + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin>>n>>q;

    vector<int> a(n+1);
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }

    int blen = sqrt(n);
    int bnum = (n + blen -1) / blen;

    vector<pii> idx(bnum+1);
    for(int i = 1;i<=bnum;i++){
        idx[i].first = (i-1)*blen+1;
        idx[i].second = min(i*blen, n);

        // cout<<idx[i].first<<" "<<idx[i].second<<endl;
    }

    for(int i=0; i<=bnum+1; i++) {
        for(int j=0; j<=bnum+1; j++) {
            brange_mx[i][j] = -inf;
            brange_mn[i][j] = inf;
        }
    }
    

    for(int i = 1;i<=bnum;i++){
        int len = idx[i].second - idx[i].first + 1;

        bpre_mx[i][0] = -inf;
        bpre_mn[i][0] = inf;
        for(int j = 1;j<=len;j++){
            int now = idx[i].first + j - 1;
            bpre_mx[i][j] = max(bpre_mx[i][j-1], a[now]);
            bpre_mn[i][j] = min(bpre_mn[i][j-1], a[now]);
        }

        bsuf_mn[i][len+1] = inf;
        bsuf_mx[i][len+1] = -inf;
        for(int j = len;j>=1;j--){
            int now = idx[i].first + j - 1;
            bsuf_mx[i][j] = max(bsuf_mx[i][j+1], a[now]);
            bsuf_mn[i][j] = min(bsuf_mn[i][j+1], a[now]);
        }

        brange_mx[i][i] = bpre_mx[i][len];
        brange_mn[i][i] = bpre_mn[i][len];
    }

    for(int i = 1;i<=bnum;i++){
        for(int j = i+1;j<=bnum;j++){
            int len = idx[j].second - idx[j].first + 1;
            brange_mx[i][j] = max(brange_mx[i][j-1], bpre_mx[j][len]);
            brange_mn[i][j] = min(brange_mn[i][j-1], bpre_mn[j][len]);
        }
    }

    while(q--){
        int c, l, r;
        cin>>c>>l>>r;
        if(c == 1) {
            int idxl = get(l, blen), idxr = get(r, blen);
            if(idxl == idxr){
                int ans = inf;
                for(int i = l;i<=r;i++){
                    ans = min(ans, a[i]);
                }
                cout<<ans<<endl;
                continue;
            }

            int idxxl = l - idx[idxl].first + 1, idxxr = r - idx[idxr].first + 1;
            int ans = min({bsuf_mn[idxl][idxxl], bpre_mn[idxr][idxxr], brange_mn[idxl+1][idxr-1]});

            cout<<ans<<endl;
        } else {
            int idxl = get(l, blen), idxr = get(r, blen);
            if(idxl == idxr){
                int ans = -inf;
                for(int i = l;i<=r;i++){
                    ans = max(ans, a[i]);
                }
                cout<<ans<<endl;
                continue;
            }

            int idxxl = l - idx[idxl].first + 1, idxxr = r - idx[idxr].first + 1;
            int ans = max({bsuf_mx[idxl][idxxl], bpre_mx[idxr][idxxr], brange_mx[idxl+1][idxr-1]});

            cout<<ans<<endl;
        }
    }



}