lizichang @ 2023-02-20 22:18:03
#include<bits/stdc++.h>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=1e6+5;
ll n,q,a[N];
struct node
{
ll maxx,l,r,col,num,p;
node()
{
l=r=col=num=p=0;//p=1所有改为num,p=2所有加col
maxx=-99999999;
}
void color(ll op,ll x)
{
if(op==1)
maxx=x,col=0,num=x,p=1;
else
{
maxx+=x;
if(p=1) num+=x;
else col+=x,p=2;
}
}
}t[N<<2];
void update(ll tr)
{
t[tr].l=t[tr<<1].l;
t[tr].r=t[tr<<1|1].r;
t[tr].maxx=max(t[tr<<1].maxx,t[tr<<1|1].maxx);
}
void push_col(ll tr)
{
if(!t[tr].p) return ;
if(t[tr].p==1)
{
t[tr<<1].color(1,t[tr].num);
t[tr<<1|1].color(1,t[tr].num);
t[tr].num=0;
t[tr].p=0;
}
else
{
t[tr<<1].color(2,t[tr].col);
t[tr<<1|1].color(2,t[tr].col);
t[tr].col=0;
t[tr].p=0;
}
}
void build(ll tr,ll l,ll r)
{
if(l==r)
{
t[tr].l=t[tr].r=l;
t[tr].maxx=a[l];
return ;
}
ll m=(l+r)>>1;
build(tr<<1,l,m);
build(tr<<1|1,m+1,r);
update(tr);
}
ll query(ll tr,ll nl,ll nr)
{
if(nl<=t[tr].l&&t[tr].r<=nr) return t[tr].maxx;
push_col(tr);
ll m=(t[tr].l+t[tr].r)>>1;
if(m>=nl)
{
if(m<nr) return max(query(tr<<1,nl,nr),query(tr<<1|1,nl,nr));
return query(tr<<1,nl,nr);
}
return query(tr<<1|1,nl,nr);
}
void modify(ll tr,ll nl,ll nr,ll op,ll x)
{
if(nl<=t[tr].l&&t[tr].r<=nr)
{
t[tr].color(op,x);
return ;
}
push_col(tr);
ll m=(t[tr].l+t[tr].r)>>1;
if(nl<=m) modify(tr<<1,nl,nr,op,x);
if(nr>m) modify(tr<<1|1,nl,nr,op,x);
update(tr);
}
int main()
{
ll op,x,y,z;
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
for(int i=1;i<=q;i++)
{
scanf("%lld%lld%lld",&op,&x,&y);
if(op!=3)
{
scanf("%lld",&z);
modify(1,x,y,op,z);
}
else
printf("%lld\n",query(1,x,y));
}
return 0;
}
by Lucky_Cloud @ 2023-04-17 14:05:12
@lizichang DALAO, 我也跟你一样20分求解答,谢谢sto