社区讨论
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 条回复,欢迎继续交流。
正在加载回复...