样例过了,为啥只有20?

P1253 扶苏的问题

Oct0pus1 @ 2022-09-26 10:38:23

#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;
const int L=1e6+10;
typedef long long ll;
struct node{
    int l,r;
    ll m,lp,la;
}t[L<<2];
ll a[L];
int n,q;
inline int read(void){
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}
inline void build(int i,int l,int r){
    t[i].l=l;t[i].r=r;t[i].la=LLONG_MIN;
    if(l==r){t[i].m=a[l];return ;}
    int mid=l+r>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    t[i].m=max(t[i<<1].m,t[i<<1|1].m);
}
inline void pushplus(int i){
    if(t[i].lp){
        t[i<<1].m+=t[i].lp;
        t[i<<1|1].l+=t[i].lp;
        t[i<<1].lp+=t[i].lp;
        t[i<<1|1].lp+=t[i].lp;
        t[i].lp=0;
    }
}
inline void pushass(int i){
    if(t[i].la!=LLONG_MIN){
        t[i<<1].m=t[i].la;
        t[i<<1|1].m=t[i].la;
        t[i<<1].lp=t[i<<1|1].lp=0;
        t[i<<1].la=t[i].la;
        t[i<<1|1].la=t[i].la;
        t[i].la=LLONG_MIN;
    }
}
inline void assign(int i,int l,int r,ll v){
    if(t[i].l>=l && t[i].r<=r){
        t[i].m=v;
        t[i].la=v;
        t[i].lp=0;
        return ;
    }
    if(t[i].l>r || t[i].r<l)return ;
    pushass(i);
    pushplus(i);
    assign(i<<1,l,r,v);
    assign(i<<1|1,l,r,v);
    t[i].m=max(t[i<<1].m,t[i<<1|1].m);
}
inline void add(int i,int l,int r,ll v){
    if(t[i].l>=l && t[i].r<=r){
        t[i].m+=v;
        t[i].lp+=v;
        return ;
    }
    if(t[i].l>r || t[i].r<l)return ;
    pushass(i);
    pushplus(i);
    add(i<<1,l,r,v);
    add(i<<1|1,l,r,v);
    t[i].m=max(t[i<<1].m,t[i<<1|1].m);
}
inline ll query(int i,int l,int r){
    if(t[i].l>=l && t[i].r<=r)return t[i].m;
    if(t[i].l>r || t[i].r<l)return LLONG_MIN;
    pushass(i);
    pushplus(i);
    return max(query(i<<1,l,r),query(i<<1|1,l,r));
}
int main(){
    n=read();q=read();
    for(register int i=1;i<=n;i++)a[i]=read();
    build(1,1,n);
    while(q--){
        register int op=read(),l=read(),r=read();register ll x;
        switch(op){
            case 1:x=read();assign(1,l,r,x);break;
            case 2:x=read();add(1,l,r,x);break;
            case 3:printf("%lld\n",query(1,l,r));break;
        }
    }
    return 0;
}

|