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

妥妥的线段树 / ST表板子题。 本蒟蒻写题时脑子抽了没想到简洁的ST表写法。 只好写线段树了。。

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

const int N = 4e6 + 10;
int a[N];
int maxx[N];
int minn[N];
void up(int i){
	maxx[i] = max(maxx[i * 2], maxx[i * 2 + 1]);
	minn[i] = min(minn[i * 2], minn[i * 2 + 1]);
}
void build(int l, int r, int i){
	if(l == r){
		maxx[i] = a[l];
		minn[i] = a[l];
	} else {
		int mid = (l + r) / 2;
		build(l, mid, i * 2);
		build(mid + 1, r, i * 2 + 1);
		up(i);
	}
}
int query_max(int jobl, int jobr, int l, int r, int i){
	if(jobl <= l && r <= jobr){
		return maxx[i];
	}
	int mid = (l + r) / 2;
	int ans = INT_MIN;
	if(jobl <= mid) ans = max(ans, query_max(jobl, jobr, l, mid, i * 2));
	if(jobr > mid) ans = max(ans, query_max(jobl, jobr, mid + 1, r, i * 2 + 1));
	return ans;
}
int query_min(int jobl, int jobr, int l, int r, int i){
	if(jobl <= l && r <= jobr){
		return minn[i];
	}
	int mid = (l + r) / 2;
	int ans = INT_MAX;
	if(jobl <= mid) ans = min(ans, query_min(jobl, jobr, l, mid, i * 2));
	if(jobr > mid) ans = min(ans, query_min(jobl, jobr, mid + 1, r, i * 2 + 1));
	return ans;
}
int n, m;
int main(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	}
	build(1, n, 1);
	while(m--){
		int op;
		cin >> op;
		if(op == 1){
			int l, r;
			cin >> l >> r;
			cout << query_min(l, r, 1, n, 1) << "\n";
		} else {
			int l, r;
			cin >> l >> r;
			cout << query_max(l, r, 1, n, 1) << "\n";
		}
	}
}

感觉本人码风还可以