线段树求最大值求卡常

回复帖子

@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;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。