4927 线段树练习5【多重标记】

#include<cstdio>
#include<iostream>
#define lc k<<1
#define rc k<<1|1
#define ll long long
using namespace std;
const ll N=2e5+5,Z=N<<2;
ll n,m,a[N];
ll sum[Z],mx[Z],mn[Z],tag[Z],set[Z],add[Z];
inline ll read(){
    ll 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-‘0‘;ch=getchar();}
    return x*f;
}
void updata(ll k){
    sum[k]=sum[lc]+sum[rc];
    mx[k]=max(mx[lc],mx[rc]);
    mn[k]=min(mn[lc],mn[rc]);
}
void pushdown(ll k,ll l,ll r){//打标记要谨慎 
    if(l==r) return ;
    ll mid=l+r>>1;
    if(add[k]){
        if(tag[lc]) set[lc]+=add[k];else add[lc]+=add[k];
        if(tag[rc]) set[rc]+=add[k];else add[rc]+=add[k];
        sum[lc]+=add[k]*(mid-l+1);
        sum[rc]+=add[k]*(r-mid);
        mn[lc]+=add[k];
        mn[rc]+=add[k];
        mx[lc]+=add[k];
        mx[rc]+=add[k];
        add[k]=0;
    }
    if(tag[k]){
        tag[lc]=tag[rc]=1;
        set[lc]=set[rc]=set[k];
        sum[lc]=set[k]*(mid-l+1);
        sum[rc]=set[k]*(r-mid);
        mn[lc]=mn[rc]=set[k];
        mx[lc]=mx[rc]=set[k];
        tag[k]=set[k]=0;
    }
}
void build(ll k,ll l,ll r){
    if(l==r){sum[k]=mx[k]=mn[k]=a[l];return ;}
    ll mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    updata(k);
}
void plusx(ll k,ll l,ll r,ll x,ll y,ll val){
    if(l==x&&r==y){
        sum[k]+=(r-l+1)*val;
        mx[k]+=val;
        mn[k]+=val;
        if(tag[k]) set[k]+=val;
        else add[k]+=val;
        return ;
    }
    pushdown(k,l,r);
    ll mid=l+r>>1;
    if(y<=mid) plusx(lc,l,mid,x,y,val);
    else if(x>mid) plusx(rc,mid+1,r,x,y,val);
    else plusx(lc,l,mid,x,mid,val),plusx(rc,mid+1,r,mid+1,y,val);
    updata(k);
}
void reset(ll k,ll l,ll r,ll x,ll y,ll val){
    if(l==x&&r==y){
        sum[k]=(r-l+1)*val;
        mx[k]=val;
        mn[k]=val;
        set[k]=val;
        tag[k]=1;
        add[k]=0;
        return ;
    }
    pushdown(k,l,r);
    ll mid=l+r>>1;
    if(y<=mid) reset(lc,l,mid,x,y,val);
    else if(x>mid) reset(rc,mid+1,r,x,y,val);
    else reset(lc,l,mid,x,mid,val),reset(rc,mid+1,r,mid+1,y,val);
    updata(k);
}
ll qsum(ll k,ll l,ll r,ll x,ll y){
    if(l==x&&r==y) return sum[k];
    pushdown(k,l,r);
    ll mid=l+r>>1;
    if(y<=mid) return qsum(lc,l,mid,x,y);
    else if(x>mid) return qsum(rc,mid+1,r,x,y);
    else return qsum(lc,l,mid,x,mid)+qsum(rc,mid+1,r,mid+1,y);
}
ll qmax(ll k,ll l,ll r,ll x,ll y){
    if(l==x&&r==y) return mx[k];
    pushdown(k,l,r);
    ll mid=l+r>>1;
    if(y<=mid) return qmax(lc,l,mid,x,y);
    else if(x>mid) return qmax(rc,mid+1,r,x,y);
    else return max(qmax(lc,l,mid,x,mid),qmax(rc,mid+1,r,mid+1,y));
}
ll qmin(ll k,ll l,ll r,ll x,ll y){
    if(l==x&&r==y) return mn[k];
    pushdown(k,l,r);
    ll mid=l+r>>1;
    if(y<=mid) return qmin(lc,l,mid,x,y);
    else if(x>mid) return qmin(rc,mid+1,r,x,y);
    else return min(qmin(lc,l,mid,x,mid),qmin(rc,mid+1,r,mid+1,y));
}
int main(){
    n=read();m=read();
    for(ll i=1;i<=n;i++) a[i]=read();
    build(1,1,n);char s[10];
    for(ll i=1,l,r,v;i<=m;i++){
        scanf("%s",s);l=read(),r=read();
        if(s[0]==‘a‘) v=read(),plusx(1,1,n,l,r,v);
        if(s[1]==‘e‘) v=read(),reset(1,1,n,l,r,v);
        if(s[1]==‘u‘) printf("%lld\n",qsum(1,1,n,l,r));
        if(s[1]==‘a‘) printf("%lld\n",qmax(1,1,n,l,r));
        if(s[1]==‘i‘) printf("%lld\n",qmin(1,1,n,l,r));
    }
    return 0;
}