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

#include <bits/stdc++.h>
#include <vector>

template <typename T, typename Merge>
struct segment_tree {
    Merge merge;
    T id_val;
    segment_tree(Merge merge, T id_val) : merge(merge), id_val(id_val) { }

    int n;
    std::vector<T> tree;

    template <typename Tp>
    void __build(int node, int l, int r, const std::vector<Tp> &list) {
        if (r - l <= 1) {
            tree[node] = list[l];
            return;
        }

        int m = l + r >> 1;
        __build(node << 1, l, m, list);
        __build(node << 1 | 1, m, r, list);
        tree[node] = merge(tree[node << 1], tree[node << 1 | 1]);
    }

    template <typename Tp>
    void build(const std::vector<Tp> &list) {
        n = list.size();
        tree = std::vector<T>(4 * n);
        __build(1, 0, n, list);
    }

    T query(int node, int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) {
            return tree[node];
        }

        if (r <= ll || rr <= l) {
            return id_val;
        }

        int m = l + r >> 1;
        T ans = id_val;
        ans = merge(ans, query(node << 1, l, m, ll, rr));
        ans = merge(ans, query(node << 1 | 1, m, r, ll, rr));
        return ans;
    }
};

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<int> vec(n);
    for (auto &e : vec) std::cin >> e;

    auto chmax = [&](int a, int b) {return std::max(a, b);};
    auto chmin = [&](int a, int b) {return std::min(a, b);};

    segment_tree<int, decltype(chmax)> maxtree(chmax, INT_MIN);
    segment_tree<int, decltype(chmin)> mintree(chmin, INT_MAX);
    maxtree.build(vec);
    mintree.build(vec);

    for (int i = 0; i < m; i++) {
        int op, l, r;
        std::cin >> op >> l >> r;
        if (op == 1) {
            std::cout << mintree.query(1, 0, n, l - 1, r) << '\n';
        } else {
            std::cout << maxtree.query(1, 0, n, l - 1, r) << '\n';
        }
    }

    return 0;
}