社区讨论

Why?我的线段树失灵了

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

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@mitmaxzo
此快照首次捕获于
2025/12/06 09:31
3 个月前
此快照最后确认于
2025/12/06 11:36
3 个月前
查看原帖
CPP
#include<cstdio>
#define Max(a,b) (((a)>(b))?(a):(b))
#define Min(a,b) (((a)<(b))?(a):(b))
#define L(i,j,k) for(int i=(j);i<=(int)(k);i++)
#define MID (l+r>>1)
#define LEFT (num<<1)
#define RIGHT (num<<1|1)
#define INF -2147483648
const int N=1e5+5;
int tree[N<<2];
int n,m;
int a[N];
void read(int& n){
	n=0;
	int x=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') x=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		n=n*10+(c-'0');
		c=getchar();
	}n*=x;
}
void build(int l,int r,int num){
	if(l==r) {
		tree[num]=a[l];
		return ;
	}
	build(l,MID,LEFT);
	build(MID+1,r,RIGHT);
	tree[num]=Max(tree[LEFT],tree[RIGHT]);
} 
int find(int l,int r,int il,int ir,int num){
	if(il>ir) return INF;
	if(il>r||ir<l) return INF;
	if(l>=il&&r<=ir){
		return tree[num];
	}
	if(ir<=MID) return find(l,MID,il,ir,LEFT);
	if(MID<il) return find(MID+1,r,il,ir,RIGHT);
	return Max(find(l,MID,il,Min(MID,ir),LEFT),find(MID+1,r,Max(MID,il),ir,RIGHT));
}
int main(){
	read(n),read(m);
	L(i,1,n){
		read(a[i]);
	}
	build(1,n,1);
	L(jdkjskjdjfs,1,m){
		int x,y;
		read(x),read(y);
		printf("%d\n",find(1,n,x,y,1));
	}
	return 0;
}

回复

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

正在加载回复...