题解 | #【模板】静态区间最值#

#include <bits/stdc++.h>
using namespace std;

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

    int n, m; if (!(cin >> n >> m)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    int LOG = 1; while ((1 << LOG) <= n) ++LOG;
    vector<int> lg(n + 1, 0); for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    vector<vector<int>> stMin(LOG, vector<int>(n + 1));
    vector<vector<int>> stMax(LOG, vector<int>(n + 1));
    for (int i = 1; i <= n; ++i) stMin[0][i] = stMax[0][i] = a[i];
    for (int k = 1; k < LOG; ++k) {
        int len = 1 << k, half = len >> 1;
        for (int i = 1; i + len - 1 <= n; ++i) {
            stMin[k][i] = min(stMin[k-1][i], stMin[k-1][i + half]);
            stMax[k][i] = max(stMax[k-1][i], stMax[k-1][i + half]);
        }
    }
    auto qMin = [&](int l, int r) {
        if (l > r) swap(l, r);
        int k = lg[r - l + 1];
        return min(stMin[k][l], stMin[k][r - (1 << k) + 1]);
    };
    auto qMax = [&](int l, int r) {
        if (l > r) swap(l, r);
        int k = lg[r - l + 1];
        return max(stMax[k][l], stMax[k][r - (1 << k) + 1]);
    };

    while (m--) {
        int op, l, r; cin >> op >> l >> r;
        if (op == 1) cout << qMin(l, r) << '\n';
        else cout << qMax(l, r) << '\n';
    }
    return 0;
}

import java.io.*;

public class Main {
    static class FastScanner {
        private final InputStream in; private final byte[] buf = new byte[1<<16];
        private int p=0, l=0; FastScanner(InputStream is){in=is;}
        private int read() throws IOException { if(p>=l){ l=in.read(buf); p=0; if(l<=0) return -1; } return buf[p++]; }
        int nextInt() throws IOException { int c; int s=1,x=0; do{c=read();}while(c<=32); if(c=='-'){s=-1;c=read();} while(c>32){ x=x*10+(c-'0'); c=read(); } return x*s; }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt();
        int m = fs.nextInt();
        int[] a = new int[n+1];
        for (int i = 1; i <= n; i++) a[i] = fs.nextInt();
        int LOG = 1; while ((1 << LOG) <= n) ++LOG;
        int[] lg = new int[n+1]; for (int i = 2; i <= n; i++) lg[i] = lg[i>>1] + 1;
        int[][] stMin = new int[LOG][n+1];
        int[][] stMax = new int[LOG][n+1];
        for (int i = 1; i <= n; i++) stMin[0][i] = stMax[0][i] = a[i];
        for (int k = 1; k < LOG; k++) {
            int half = 1 << (k-1);
            for (int i = 1; i + (1<<k) - 1 <= n; i++) {
                stMin[k][i] = Math.min(stMin[k-1][i], stMin[k-1][i + half]);
                stMax[k][i] = Math.max(stMax[k-1][i], stMax[k-1][i + half]);
            }
        }
        StringBuilder out = new StringBuilder();
        while (m-- > 0) {
            int op = fs.nextInt();
            int l = fs.nextInt();
            int r = fs.nextInt();
            if (l > r) { int t=l; l=r; r=t; }
            int k = lg[r - l + 1];
            if (op == 1) {
                int ans = Math.min(stMin[k][l], stMin[k][r - (1<<k) + 1]);
                out.append(ans).append('\n');
            } else {
                int ans = Math.max(stMax[k][l], stMax[k][r - (1<<k) + 1]);
                out.append(ans).append('\n');
            }
        }
        System.out.print(out.toString());
    }
}

import sys

data = sys.stdin.buffer.read().split()
it = iter(data)
n = int(next(it)); m = int(next(it))
a = [0] * (n + 1)
for i in range(1, n + 1):
    a[i] = int(next(it))

LOG = 1
while (1 << LOG) <= n:
    LOG += 1
lg = [0] * (n + 1)
for i in range(2, n + 1):
    lg[i] = lg[i >> 1] + 1

stMin = [[0] * (n + 1) for _ in range(LOG)]
stMax = [[0] * (n + 1) for _ in range(LOG)]
for i in range(1, n + 1):
    stMin[0][i] = a[i]
    stMax[0][i] = a[i]
for k in range(1, LOG):
    seg_len = 1 << k
    half = seg_len >> 1
    # i in [1, n-seg_len+1]
    for i in range(1, n - seg_len + 2):
        stMin[k][i] = min(stMin[k-1][i], stMin[k-1][i + half])
        stMax[k][i] = max(stMax[k-1][i], stMax[k-1][i + half])

out_lines = []
for _ in range(m):
    op = int(next(it)); l = int(next(it)); r = int(next(it))
    if l > r:
        l, r = r, l
    k = lg[r - l + 1]
    if op == 1:
        ans = min(stMin[k][l], stMin[k][r - (1 << k) + 1])
    else:
        ans = max(stMax[k][l], stMax[k][r - (1 << k) + 1])
    out_lines.append(str(ans))
sys.stdout.write('\n'.join(out_lines))