wyf_ @ 2023-11-10 21:55:08
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
struct node{
int l,r,v,laz1,laz2,sum,mx;
}a[4*maxn];
int n,q,b[maxn];
int read()
{
int 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<<1)+(x<<3)+(ch-'0');
ch=getchar();
}
return x*f;
}
void t_build(int l,int r,int v)
{
a[v].l=l;
a[v].r=r;
a[v].laz1=0;
a[v].laz2=0;
if(l==r)
{
a[v].mx=b[l];
return ;
}
int mid=(l+r)>>1;
t_build(l,mid,v<<1);
t_build(mid+1,r,(v<<1)|1);
a[v].mx=max(a[v<<1].mx,a[(v<<1)|1].mx);
return ;
}
void update(int x,int y,int v,int k,bool flag)
{
if(!flag)
{
if(a[v].l>=x&&a[v].r<=y)
{
a[v].laz1=k;
a[v].laz2=0;
a[v].mx=k;
return ;
}
if(a[v].laz1)
{
a[v<<1].laz1=a[v].laz1;
a[v<<1].laz2=0;
a[(v<<1)|1].laz1=a[v].laz1;
a[(v<<1)|1].laz2=0;
a[v].laz1=0;
a[v].laz2=0;
}
int mid=(a[v].r+a[v].l)>>1;
if(y<=mid) update(x,y,v<<1,k,0);
else if(x>mid) update(x,y,(v<<1)|1,k,0);
else{
update(x,mid,v<<1,k,0);
update(mid+1,y,(v<<1)|1,k,0);
}
}//修改
else if(flag)
{
if(a[v].l>=x&&a[v].r<=y)
{
a[v].laz1=0;
a[v].laz2+=k;
a[v].mx=a[v].mx+k;
return ;
}
if(a[v].laz2)
{
a[v<<1].laz2+=a[v].laz2;
a[v<<1].laz1=0;
a[(v<<1)|1].laz2+=a[v].laz2;
a[(v<<1)|1].laz1=0;
a[v].laz2=0;
a[v].laz1=0;
}
int mid=(a[v].r+a[v].l)>>1;
if(y<=mid) update(x,y,v<<1,k,1);
else if(x>mid) update(x,y,(v<<1)|1,k,1);
else{
update(x,mid,v<<1,k,1);
update(mid+1,y,(v<<1)|1,k,1);
}
}//加数
a[v].mx=max(a[v<<1].mx,a[(v<<1)|1].mx);
return ;
}
int t_find(int x,int y,int v)
{
if(a[v].l>=x&&a[v].r<=y)
{
if(a[v].laz1) return a[v].laz1;
else if(a[v].laz2) return a[v].laz2+a[v].mx;
else return a[v].mx;
}
if(a[v].laz1)
{
a[v<<1].laz1=a[v].laz1;
a[v<<1].laz2=0;
a[(v<<1)|1].laz1=a[v].laz1;
a[(v<<1)|1].laz2=0;
a[v].laz1=0;
a[v].laz2=0;
}
else if(a[v].laz2)
{
a[v<<1].laz2+=a[v].laz2;
a[v<<1].laz1=0;
a[(v<<1)|1].laz2+=a[v].laz2;
a[(v<<1)|1].laz1=0;
a[v].laz2=0;
a[v].laz1=0;
}
int mid=(a[v].l+a[v].r)>>1;
if(y<=mid) return t_find(x,y,v<<1);
else if(x>mid) return t_find(x,y,(v<<1)|1);
else{
return max(t_find(x,mid,v<<1),t_find(mid+1,y,(v<<1)|1));
}
}
int main()
{
n=read();
q=read();
for(int i=1;i<=n;i++) b[i]=read();
t_build(1,n,1);
while(q--)
{
int op,x,y,k;
op=read();
if(op==1)
{
x=read(),y=read(),k=read();
update(x,y,1,k,0);
}
else if(op==2)
{
x=read(),y=read(),k=read();
update(x,y,1,k,1);
}
else {
x=read(),y=read();
cout<<t_find(x,y,1)<<endl;
}
}
return 0;
}
只过了#1,玄关
by tjr0513 @ 2023-11-10 21:59:42
修改操作每次两个懒标记都要下传
by 西湖水妖 @ 2023-11-11 10:11:08
《玄关》。