线段树求最大值求卡常

@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:09 回复举报

这边建议您学 $\rm ST$ 表呢！

@wqy_03 2021-01-13 15:19 回复举报

这边建议您学 $ST$ 表呢！O(1) !

@LiBoyi 2021-01-13 15:26 回复举报

@hhoppitree 学校OJ专题上的必须要用线段树qwq

@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;
}

@Wmlj__ytm 2021-01-13 15:45 回复举报

@LiBoyi自己手写一个max函数应该会快一点

@hhoppitree 2021-01-13 15:45 回复举报

@LiBoyi

@hhoppitree 2021-01-13 15:46 回复举报

还是不行的话我再进行终极卡常

@LiBoyi 2021-01-13 15:58 回复举报

@hhoppitree ok了谢谢您%%%