社区讨论

求助,T了

P3865【模板】ST 表 & RMQ 问题参与者 6已保存回复 20

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
20 条
当前快照
1 份
快照标识符
@mi85xz4u
此快照首次捕获于
2025/11/21 09:10
4 个月前
此快照最后确认于
2025/11/21 09:46
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define max_(a,b) a>b?a:b;
using namespace std;
const int MAXN=100000;
int n,m;
struct node{
	int l,r,maxx;
}tree[MAXN*4+1];
inline int read(){
	int x=0;bool f=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return f?-x:x;
}
void build(int l,int r,int now){
	tree[now].l=l,tree[now].r=r;
	if(l==r){
		tree[now].maxx=read();
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,now<<1);build(mid+1,r,now<<1|1);
	tree[now].maxx=max_(tree[now<<1].maxx,tree[now<<1|1].maxx);
}
int ask_range(int x,int y,int now){
	if(tree[now].l>=x&&tree[now].r<=y){
		return tree[now].maxx;
	}
	int mid=(tree[now].l+tree[now].r)>>1,ans=-10000000;
	if(x<=mid) ans=max_(ans,ask_range(x,y,now<<1));
	if(y>mid) ans=max_(ans,ask_range(x,y,now<<1|1));
	return ans;
}

int main(){
	n=read(),m=read();
	build(1,n,1);
	int x,y;
	while(m--){
		x=read(),y=read();
		printf("%d\n",ask_range(x,y,1));
	}
	return 0;
}

回复

20 条回复,欢迎继续交流。

正在加载回复...