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

虽然st表，但是线段树能维护的东西太多了，看见区间查询就甩线段树了

不过真的会有题卡这个常数吗？不太懂

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e6 + 10;

template<class T>
struct SegmentTree {
    struct Info {
        pii val;
        Info(){}
        Info(T num): val(num) {}
        Info operator+(const Info& x) const {
            Info y;
            y.val.first = max(val.first, x.val.first);
            y.val.second = min(val.second, x.val.second);
            return y;
        }
        void operator+=(const Info& x) {
            *this = *this + x;
        }
    };

    int min_, max_;
    vector<Info> info;
    SegmentTree(int n): min_(1), max_(n), info(4 * n) {}
    SegmentTree(int l, int r): min_(l), max_(r), info(4 * (r - l + 1)) {}
private:
    void pull(int i) {
        info[i] = info[2 * i] + info[2 * i + 1];
    }
    void set(int pos, Info v, int i, int l, int r) {
        if (l == r) {info[i] = v; return;}
        if (pos <= l + (r - l) / 2) set(pos, v, 2 * i, l, l + (r - l) / 2);
        else set(pos, v, 2 * i + 1, l + (r - l) / 2 + 1, r);
        pull(i);
    }
    void add(int pos, Info v, int i, int l, int r) {
        if (l == r) {info[i] += v; return;}
        if (pos <= l + (r - l) / 2) add(pos, v, 2 * i, l, l + (r - l) / 2);
        else add(pos, v, 2 * i + 1, l + (r - l) / 2 + 1, r);
        pull(i);
    }
    Info query(int x, int y, int i, int l, int r) {
        if (l >= x && r <= y) return info[i];
        if (y <= l + (r - l) / 2) return query(x, y, 2 * i, l, l + (r - l) / 2);
        if (x > l + (r - l) / 2) return query(x, y, 2 * i + 1, l + (r - l) / 2 + 1, r);
        return query(x, y, 2 * i, l, l + (r - l) / 2) + query(x, y, 2 * i + 1, l + (r - l) / 2 + 1, r);
    }
    int binarySearch(int i, int l, int r) {
        if (l == r) return l;
        if (info[2 * i].v <= 0) return binarySearch(2 * i, l, l + (r - l) / 2);
        return binarySearch(2 * i + 1, l + (r - l) / 2 + 1, r);
    }
public:
    void set(int i, T v) {
        set(i, v, 1, min_, max_);
    }
    void add(int i, Info v) {
        add(i, v, 1, min_, max_);
    }
    Info query(int l, int r) {
        return query(l, r, 1, min_, max_);
    }
    int binarySearch() {
        return binarySearch(1, min_, max_);
    }
    friend ostream& operator<<(ostream& os, SegmentTree& seg) {
        os << "seg[";
        for (int i = seg.min_; i <= seg.max_; i++) {
            os << seg.query(i, i).sum << ",";
        }
        os << ']';
        return os;
    }
};

void solve()
{	
    int n,q;
    cin>>n>>q;
    SegmentTree<pii> t(n);
    for (int i = 0 ; i < n ; i++)
    {
        int a;
        cin>>a;
        t.set(i + 1,{a,a});
    }
    while(q--)
    {
        int op,l,r;
        cin>>op>>l>>r;
        if (op == 1) cout<<t.query(l,r).val.second<<'\n';
        if (op == 2) cout<<t.query(l,r).val.first<<'\n';
    }
    return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int _ = 1;
    //std::cin>>_;
    while (_--)
    {
        solve();
    }
    return 0;
}