P1816 忠诚 题解

题目大意

有一个长度为 \(n\) 的序列，共 \(m\) 次查询，每次查询序列中 \(l\) 到 \(r\) 中最小值。

思路

显然线段树，3分钟切了。

#include
using namespace std;

const int maxn = 2e5 + 10;

int minv[maxn * 4], a[maxn];

void pushup(int id) {
	minv[id] = min(minv[id << 1], minv[id << 1 | 1]);
}
void build(int id, int l, int r) {
	if (l == r) {
		minv[id] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	pushup(id);
	return;
}
int query(int id, int l, int r, int x, int y) {
	if (x <= l && r <= y) {
		return minv[id];
	}
	int mid = (l + r) >> 1;
	int ans = 0x7fffffff;
	if (x <= mid) {
		ans = min(ans, query(id << 1, l, mid, x, y));
	}
	if (y > mid) {
		ans = min(ans, query(id << 1 | 1, mid + 1, r, x, y));
	}
	return ans;
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		cin >> a[i];
	}
	build(1, 1, n);
	while (m--) {
	    int l, r;
	    cin >> l >> r;
	    cout << query(1, 1, n, l, r) << ' ';
	}
	return 0;
}