线段树93分求救
查看原帖
线段树93分求救
705296
miffy_123楼主2024/10/14 19:27

真没救了吗?

#include <bits/stdc++.h>
#define int long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define rep(i,l,r) for(register int i(l);i<=r;++i)
#define per(i,r,l) for(register int i(r);i>=l;--i)
using namespace std;
int n,m,a[100005];
struct tree{
    int l,r,big,lazy_tag;
}t[400005];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
inline void push_up(int p){
    t[p].big=max(t[ls(p)].big,t[rs(p)].big);
}
inline void push_down(int p){
	if(t[p].lazy_tag!=0){
	    t[ls(p)].lazy_tag+=t[p].lazy_tag,t[ls(p)].big+=t[p].lazy_tag;
    	t[rs(p)].lazy_tag+=t[p].lazy_tag,t[rs(p)].big+=t[p].lazy_tag;
	    t[p].lazy_tag=0;
	}
}
inline void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].big=a[l];
        return;
    }
    int mid=l+r>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}
inline void update(int p,int l,int r,int val){
    if(t[p].r<l||t[p].l>r)return;
    if(t[p].l>=l&&t[p].r<=r){
        t[p].big+=val,t[p].lazy_tag+=val;
        return ;
    }
    push_down(p);
    update(ls(p),l,r,val);
    update(rs(p),l,r,val);
    push_up(p);
}
inline int ask(int p,int l,int r){
    if(t[p].r<l||t[p].l>r)return 0;
    if(t[p].l>=l&&t[p].r<=r)return t[p].big;
	int ret=0;
    push_down(p);
    ret=max(ret,ask(ls(p),l,r));
    ret=max(ret,ask(rs(p),l,r));
    push_up(p);
    return ret;
}
signed main() {
    n=read(),m=read();
    rep(i,1,n)a[i]=read();
    build(1,1,n);
    rep(i,1,m){
        int l=read(),r=read();
        printf("%d\n",ask(1,l,r));
    }
	return 0;
}
2024/10/14 19:27
加载中...