某idol的人气调查

暴力也有分！！！

题目背景

最近蔡徐坤非常烦恼因为总是有人喜欢黑他

于是蔡徐坤化名菜虚鲲暗中来到 x湖一中进行人气调查

这个学校的学生对于蔡徐坤有这样的特点

一开始每个人的恶意值都为0

如果一个人黑他这个学生周围的一片人就会累加 x点恶意值

蔡徐坤会随机时间调查一群人的恶意值最大的那个人

当蔡徐坤看不下去了就会给一部分人发律师函警告这些学生的恶意值就会清零

由于鸡你实在是太美

请你这只鸡模拟这一过程

题目描述 & 格式

第一行 n表示学生数 m表示事件个数

接下来m行

每行3或4个数 op,L,R (v)

若op=1 请输出区间

若op=2 表示将区间

若op=3 表示区间

提示

初始化时修改标记要置为-1(因为会有0出现）！！切记

这题的pushdown需要修改

如果一个点上有区间修改标记

那么我们只需要考虑修改标记，

下传时把左右子节点的加法标记清零

如果一个点上只有加法标记

正常下传加法标记

但是需要考虑它的左子节点和右子节点上有修改标记的情况

如果这个节点上有修改标记,我们只需要在修改标记上+add[o]即可,不用考虑加法标记

否则照常让加法标记 +add[o]

这题的modify也要修改

考虑递归到目标节点时

如果这个节点上有修改标记,我们只需要在修改标记上+v即可,不用考虑加法标记

否则照常让加法标记 +v

如何写区间修改操作呢

考虑递归到目标节点时

将该点的最值，加法标记，修改标记全部置0即可

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

struct node{
    int v,mul,add;
}st[4000005];


inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}


void pushdown(int k){
    int ls=k<<1,rs=k<<1|1;
    st[ls].v*=st[k].add;
    st[rs].v*=st[k].add;
    st[ls].mul*=st[k].add;
    st[rs].mul*=st[k].add;
    st[ls].add*=st[k].add;
    st[rs].add*=st[k].add;
    st[ls].v+=st[k].mul;
    st[rs].v+=st[k].mul;
    st[ls].mul+=st[k].mul;
    st[rs].mul+=st[k].mul;
    st[k].add=1;
    st[k].mul=0;
}

void ud1(int hhh,int stdl,int stdr,int l,int r){
    if(r<stdl||stdr<l){
        return ;
    }
    if(l<=stdl && stdr<=r){
        st[hhh].v=0;
        st[hhh].mul=0;
        st[hhh].add=0;
        return ;
    }
    if(st[hhh].mul||!st[hhh].add){
        pushdown(hhh);
    }
    int m=(stdl+stdr)/2;
    ud1(hhh*2,stdl,m,l,r);
    ud1(hhh*2+1,m+1,stdr,l,r);
    st[hhh].v=max(st[hhh*2].v,st[hhh*2+1].v);
    return;
}

void ud2(int hhh,int stdl,int stdr,int l,int r,int k){
    if(r<stdl||stdr<l){
        return;
    }
    if(l<=stdl && stdr<=r){
        st[hhh].mul+=k;
        st[hhh].v+=k;
        return ;
    }
    if(st[hhh].mul||!st[hhh].add){
        pushdown(hhh);
    }
    int m=(stdl+stdr)/2;
    ud2(hhh*2,stdl,m,l,r,k);
    ud2(hhh*2+1,m+1,stdr,l,r,k);
    st[hhh].v=max(st[hhh*2].v,st[hhh*2+1].v);
    return;
}

int query(int hhh,int stdl,int stdr,int l,int r){
    if(r<stdl||stdr<l){
        return 0;
    }
    if(l<=stdl&&stdr<=r){
        return st[hhh].v;
    }
    if(st[hhh].mul||!st[hhh].add){
        pushdown(hhh);
    }
    int m=(stdl+stdr)/2;
    return max(query(hhh*2,stdl,m,l,r),query(hhh*2+1,m+1,stdr,l,r));
}

int main(){ 
    int n, m;
    n=read();
    m=read();
    for(int i=1;i<=4*n;i++){
        st[i].add=1;
    }
    while(m--){
        int chk;
        chk=read();
        int x, y;
        int k;
        if(chk==2){
            x=read();
            y=read();
            ud1(1,1,n,x,y);
        }
        if(chk==3){
            x=read();
            y=read();
            k=read();
            ud2(1,1,n,x,y,k);
        }
        if(chk==1){
            x=read();
            y=read();
            printf("%d
",query(1,1,n,x,y));
        }
    }
    return 0;
}