# 线段树求最大值求卡常

• 版块灌水区
• 楼主
• 发帖时间2021-01-13 14:43
@LiBoyi  2021-01-13 14:43 回复

rt

#include<bits/stdc++.h>

using namespace std;

inline int read(){
int w=0,f=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
while(isdigit(ch)){
w=(w<<3)+(w<<1)+(ch^48);
ch=getchar();
}
return w*f;
}

int n,q;
int a[100005],t[400005];
inline int ls(int p){
return p<<1;
}
inline int rs(int p){
return p<<1|1;
}
void pushup(int p){
t[p]=max(t[ls(p)],t[rs(p)]);
}
void build(int p,int l,int r){
if(l==r){
t[p]=max(t[p],a[l]);
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
pushup(p);
}
int query(int p,int l,int r,int tl,int tr){
int res=-1e9;
if(tl<=l&&r<=tr)
return t[p];
int mid=(l+r)>>1;
if(tl<=mid)
res=max(res,query(ls(p),l,mid,tl,tr));
if(tr>mid)
res=max(res,query(rs(p),mid+1,r,tl,tr));
return res;
}

int main(){
n=read();
n++;
for(int i=1;i<=n;i++) a[i]=read();
build(1,1,n);
q=read();
for(int i=1;i<=q;i++){
int x=read(),y=read();
printf("%d\n",query(1,1,n,x+1,y+1));
}
return 0;
}
@hhoppitree  2021-01-13 15:45 回复 举报
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")

using namespace std;

inline int read(){
int res=0;
bool zf=0;
char c;
while(((c=getchar())<'0'||c>'9')&&c!='-');
if(c=='-')zf=1;
else res=c-'0';
while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
if(zf)return -res;
return res;
}

int n,q;
int a[100005],t[400005];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define pushup(x) (t[x]=(t[ls(x)]>t[rs(x)]?t[ls(x)]:t[rs(x)]))
void build(int p,int l,int r){
if(l==r){
t[p]=a[l];
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
pushup(p);
}
int query(int p,int l,int r,int tl,int tr){
int res=-1e9;
if(tl<=l&&r<=tr)
return t[p];
int mid=(l+r)>>1,tmp;
if(tl<=mid)
(((tmp=query(ls(p),l,mid,tl,tr))>res)?res=tmp:0);
if(tr>mid)
(((tmp=query(rs(p),mid+1,r,tl,tr))>res)?res=tmp:0);
return res;
}

int main(){
n=read();
++n;
for(register int i=1;i<=n;++i) a[i]=read();
build(1,1,n);
q=read();
for(register int i=1;i<=q;++i){
int x=read(),y=read();
printf("%d\n",query(1,1,n,x+1,y+1));
}
return 0;
}