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