吉司机线段树.    

注意一定要 pushdown

code:  

#include <cstdio> 
#include <algorithm> 
#include <cstring>      
#define ll long long   
#define lson x<<1  
#define rson x<<1|1        
#define N 300007   
#define I(s) freopen(s".in","r",stdin) 
#define O(s) freopen(s".out","w",stdout)  
#define setIO(s) I(s),O(s) 
using namespace std;     
const ll inf=1ll<<60;    
int n,m;        
int mi[N<<2],len[N<<2];  
ll add[N<<2],tag[N<<2],mn[N<<2],sn[N<<2];   
void pushup(int x) 
{
    if(mn[lson]<mn[rson])  mn[x]=mn[lson],mi[x]=mi[lson],sn[x]=min(sn[lson],mn[rson]);
    if(mn[rson]<mn[lson])  mn[x]=mn[rson],mi[x]=mi[rson],sn[x]=min(sn[rson],mn[lson]);   
    if(mn[lson]==mn[rson]) mn[x]=mn[lson],mi[x]=mi[lson]+mi[rson],sn[x]=min(sn[lson],sn[rson]);   
}
void build(int l,int r,int x) 
{            
    add[x]=0,tag[x]=inf,len[x]=r-l+1;      
    if(l==r)  
    {
        scanf("%lld",&mn[x]),sn[x]=inf,mi[x]=1;                    
        return;  
    }
    int mid=(l+r)>>1;   
    build(l,mid,lson),build(mid+1,r,rson);   
    pushup(x);        
}             
void mark_tag(int x,ll v) 
{    
    add[x]=0,tag[x]=v,mn[x]=v,sn[x]=inf,mi[x]=len[x];      
}  
void mark_add(int x,ll v) 
{   
    add[x]+=v,mn[x]+=v,sn[x]+=v;      
} 
void pushdown(int x) 
{        
    if(tag[x]!=inf)  
    {
        mark_tag(lson,tag[x]);   
        mark_tag(rson,tag[x]);   
    }   
    if(add[x]) 
    {
        mark_add(lson,add[x]); 
        mark_add(rson,add[x]); 
    }      
    mn[lson]=max(mn[lson],mn[x]);  
    mn[rson]=max(mn[rson],mn[x]);          
    add[x]=0,tag[x]=inf;  
}       
void modify(int l,int r,int x,int L,int R,ll v) 
{ 
    if(l>=L&&r<=R)   
    {
        mark_tag(x,v);    
        return; 
    }  
    pushdown(x); 
    int mid=(l+r)>>1;  
    if(L<=mid)  modify(l,mid,lson,L,R,v); 
    if(R>mid)   modify(mid+1,r,rson,L,R,v);   
    pushup(x); 
} 
void addv(int l,int r,int x,int L,int R,ll v) 
{
    if(l>=L&&r<=R) 
    {
        mark_add(x,v);   
        return; 
    } 
    pushdown(x);  
    int mid=(l+r)>>1;  
    if(L<=mid)  addv(l,mid,lson,L,R,v); 
    if(R>mid)   addv(mid+1,r,rson,L,R,v);   
    pushup(x);   
}   
void getmax(int l,int r,int x,int L,int R,ll v) 
{
    if(mn[x]>=v)  return;   
    if(l>=L&&r<=R&&sn[x]>v) 
    {
        mn[x]=v;   
        return;  
    }  
    pushdown(x); 
    int mid=(l+r)>>1;  
    if(L<=mid)  getmax(l,mid,lson,L,R,v); 
    if(R>mid)   getmax(mid+1,r,rson,L,R,v);  
    pushup(x);   
}
int query(int l,int r,int x,int L,int R) 
{
    if(l>=L&&r<=R) return mn[x]?0:mi[x];   
    pushdown(x); 
    int mid=(l+r)>>1,re=0;   
    if(L<=mid)  re+=query(l,mid,lson,L,R); 
    if(R>mid)   re+=query(mid+1,r,rson,L,R); 
    return re;    
}
int main() 
{ 
    // setIO("input");           
    scanf("%d%d",&n,&m);            
    build(1,n,1);      
    for(int i=1;i<=m;++i) 
    { 
        ll z; 
        int op,l,r;   
        scanf("%d%d%d",&op,&l,&r);   
        if(op==1)  scanf("%lld",&z),modify(1,n,1,l,r,z);   
        if(op==2)  scanf("%lld",&z),addv(1,n,1,l,r,z),getmax(1,n,1,l,r,0ll);    
        if(op==3)  printf("%d\n",query(1,n,1,l,r));   
    }
    return 0;
}