专栏文章

题解：P3865 【模板】ST 表 && RMQ 问题

jjzl_1210
P3865题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipaht0h
此快照首次捕获于
2025/12/03 08:49
3 个月前
此快照最后确认于
2025/12/03 08:49
3 个月前
查看原文
这是一篇线段树题解。
虽然题目的查询复杂度必须为 O(1)O(1)，而线段树查询复杂度 O(log⁡n)O(\log n)，但我偏不信邪，试一试才知道。

前置知识

线段树，模板题传送门。

具体实现

根据题面意思，很容易就可以写出建树，查询的部分。其实和加法的逻辑是一样的。
注意到，这道题目不需要修改数值，所以就没有懒标记、修改函数。最难的懒标记都没有了，剩下的岂不是简简单单。
由于线段树常数较大，且查询复杂度为 O(log⁡n)O(\log n)，那么就需要用到快读优化，我在题面给的快读上又加了一点小小的改动：
CPP
inline int read(){
	int x = 0, f = 1;char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
	//改动的地方，把 x*10+ch-48 用位运算表示，这样速度会更快一点。 
	return x * f;
}

代码

于是我们就轻轻松松卡常过了这道题目，下面是代码。
CPP
#include <bits/stdc++.h>
#define ld p << 1
#define rd p << 1 | 1
using namespace std;
const int N = 1e5 + 5;
inline int read(){
	int x = 0, f = 1;char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
	return x * f;
}
struct Node{
	int l, r, zd;
} t[N << 2];
int n, Q, a[N];
void push_up(int p){
	t[p].zd = max(t[ld].zd, t[rd].zd);
}
void build(int p, int l, int r){//建树 
	t[p] = (Node) {l, r, a[l]};
	if(l == r) return;
	int mid = l + r >> 1;
	build(ld, l, mid);
	build(rd, mid + 1, r);
	push_up(p);
}
int ask(int p, int l, int r){//查询 
	if(l <= t[p].l && t[p].r <= r){
		return t[p].zd;
	}
	int mid = t[p].l + t[p].r >> 1, ans = -1;
	if(l <= mid) ans = max(ans, ask(ld, l, r));
	if(r > mid) ans = max(ans, ask(rd, l, r));
	return ans;
}
int main(){
	n = read(), Q = read();
	for(int i = 1;i <= n;i++) a[i] = read();
	build(1, 1, n);
	while(Q--){
		int l = read(), r = read();
		printf("%d\n", ask(1, l, r));
	}
	return 0;
}
不过既然这是 ST 表的模板题，肯定要尊重一下，下面贴一下正解，如何实现可以去看其他题解。
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
inline int read(){
	int x = 0, f = 1;char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
	return x * f;
}
int n, m, lg[N], f[N][22];
int main(){
	n = read(), m = read();
	for(int i = 2;i <= n;i++) lg[i] = lg[i / 2] + 1;
	for(int i = 1;i <= n;i++){
		f[i][0] = read();
	}
	for(int j = 1;j <= lg[n];j++){
		for(int i = 1;i + (1 << j) - 1 <= n;i++){
			f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
		}
	}
	for(int i = 1;i <= m;i++){
		int l = read(), r = read(), lgc, maxl, maxr;
		lgc = lg[r - l + 1];
		maxl = f[l][lgc], maxr = f[r - (1 << lgc) + 1][lgc];
		printf("%d\n", max(maxl, maxr));
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...