【2024.10.3练习】模拟询问程序

题目描述

---

题目分析

求区间最值考虑使用线段树。由于n的最大值为，因此MAX_N取。

---

我的代码

使用线段树尤其需要注意下标。

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 2 << 20;
int st[MAX_N];	//线段树
int n = 0;	//学生数（叶子结点个数）
int l = 1;  //线段树维护的长度为[0,l)
int m;	//操作数
//初始化线段树
void init() {
	while (l < n) {
		l *= 2;
	}
	for (int i = 0; i < MAX_N; i++)
	{
		st[i] = -1;
	}
}
//更新结点
void update(int k, int a) {
	k += l - 1;
	st[k] = a;
	while (k > 0) {
		k = (k - 1) / 2;
		st[k] = max(st[k * 2 + 1], st[k * 2 + 2]);
	}
}
//查询操作
int query(int a, int b, int k, int l, int r) {
	if (b <= l || a >= r) {
		return -1;
	}
	if (l >= a && r <= b) {
		return st[k];
	}
	else {
		int query_lson = query(a, b, 2 * k + 1, l, (l + r) / 2);
		int query_rson = query(a, b, 2 * k + 2, (l + r) / 2, r);
		return max(query_lson, query_rson);
	}
}
int main() {
	cin >> n >> m;
	init();

	//初始化线段树
	for (int i = 0; i < n; i++)
	{
		int score;
		cin >> score;
		update(i, score);
	}
	//查询和更新操作
	for (int i = 0; i < m; i++)
	{
		char p;
		int a;
		int b;
		cin >> p >> a >> b;
		if (p == 'Q') {
			cout << query(a - 1, b, 0, 0, l) << endl;
		}
		else if (p == 'U') {
			if (st[a + l - 2] < b) {
				update(a - 1, b);
			}
		}
	}
	return 0;
}