区间修改 + 区间最大子段和

$100000$ 的数据错了 $4$ 个。

#include<bits/stdc++.h>
using namespace std;
namespace IO{
...
}
using IO::read;
using IO::write;
const int MAXN=1e5+5;
struct node{
    int lmax,rmax,sum,dat,tag;
    int l,r;
}t[MAXN<<2];
int z[MAXN];
void push_up(int p)
{
	t[p].sum=(t[p<<1].sum+t[p<<1|1].sum);
    t[p].lmax=max(t[p<<1].lmax,t[p<<1].sum+t[p<<1|1].lmax);
    t[p].rmax=max(t[p<<1|1].rmax,t[p<<1|1].sum+t[p<<1].rmax);
    t[p].dat=max(max(t[p<<1].dat,t[p<<1|1].dat),t[p<<1].rmax+t[p<<1|1].lmax);
}
void push_down(int p)
{
	if(t[p].tag)
	{
		int mid=(t[p].l+t[p].r)>>1;
		t[p<<1].tag=t[p].tag;
		t[p<<1|1].tag=t[p].tag;
		t[p<<1].sum=(mid-t[p].l+1)*t[p].tag;
		t[p<<1|1].sum=(t[p].r-mid)*t[p].tag;
		t[p<<1].dat=t[p<<1].lmax=t[p<<1].rmax=max(t[p<<1].sum,t[p].tag);
		t[p<<1|1].dat=t[p<<1|1].lmax=t[p<<1|1].rmax=max(t[p<<1|1].sum,t[p].tag);
		t[p].tag=0;
	}
}
void build(int p,int l,int r)
{
    t[p].l=l; t[p].r=r;
    if(l==r)
	{
        t[p].sum=t[p].dat=t[p].lmax=t[p].rmax=z[l];
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    push_up(p);
}
void modify(int p,int l,int r,int k)
{
    if(l<=t[p].l&&t[p].r<=r)
	{
        t[p].tag=k;
        t[p].sum=(t[p].r-t[p].l+1)*t[p].tag;
        t[p].dat=t[p].lmax=t[p].rmax=k>0?t[p].sum:k;
        return;
    }
    int mid=(t[p].l+t[p].r)>>1;
    push_down(p);
    if(l<=mid) modify(p<<1,l,r,k);
    if(r>mid) modify(p<<1|1,l,r,k);
	push_up(p);
} 
node query(int p,int l,int r)
{
    if(t[p].l>=l&&t[p].r<=r) return t[p];
    int mid=(t[p].l+t[p].r)>>1,val=-(1<<30);
    node a,b,c;
    a.lmax=a.rmax=a.sum=a.dat=val;
    b.dat=b.lmax=b.rmax=b.sum=val;
    c.sum=0;
    push_down(p);
    if(l<=mid)
	{
        a=query(p<<1,l,r);
        c.sum+=a.sum;
    }
    if(r>mid)
	{
        b=query(p<<1|1,l,r);
        c.sum+=b.sum;
    }
    c.dat=max(max(max(a.dat,b.dat),a.rmax+b.lmax),0);
    c.lmax=max(a.lmax,b.lmax+a.sum);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    if(l>mid) c.lmax=max(c.lmax,b.lmax);
    if(r<=mid) c.rmax=max(c.rmax,a.rmax);
    return c;
}
int n,m;
signed main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.txt","w",stdout);
    read(n); read(m);
    for(int i=1;i<=n;i++) read(z[i]);
    build(1,1,n);
    int l,r,x,op;
    for(int i=1;i<=m;i++)
	{
        read(op); read(l); read(r);
        if(op==1)
        {
        	read(x);
        	modify(1,l,r,x);
		}
        else write(query(1,l,r).dat),putchar('\n');
    }
}