zyzbldnb @ 2023-01-16 21:00:04
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e+6,inf=0x3f3f3f3f3f;
ll t1[4*maxn+5],t2[4*maxn+5],w[4*maxn+5],a[maxn];
int n,q;
bool c[4*maxn+5];
void build(int u,int l,int r)
{
if(r==l)
{w[u]=a[l];return;}
int mid=(l+r)/2;
build(2*u,l,mid);
build(2*u+1,mid+1,r);
w[u]=max(w[2*u],w[2*u+1]);
}
void tag1(int u,int x) //= 赋值x
{
t1[u]=x;c[u]=1;
t2[u]=0; // 覆盖掉了
w[u]=x;
}
void tag2(int u,int x)//+x
{
if(c[u]!=0) t1[u]+=x;
else t2[u]+=x;
w[u]+=x; // 最大值加x
}
void pushdown(int u)
{
if(c[u]!=0) // 赋值了
{
tag1(2*u,t1[u]);tag1(2*u+1,t1[u]);//一定要优先t1,是覆盖,没有覆盖才是+
c[u]=0;//
}
else {
tag2(2*u,t2[u]);
tag2(2*u+1,t2[u]);
t2[u]=0;
}
}
int query(int u,int l,int r, int x,int y)
{
if(x<=l&&r<=y) return w[u];
else if(!(x>r||y<l) )
{
int mid=(l+r)/2;
pushdown(u);
return max(query(2*u,l,mid,x,y),query(2*u+1,mid+1,r,x,y));
}
else return -inf;
}
void update(int u,int l,int r,int x, int y, int xx,int opt)
{
if(x<=l&&r<=y)
{
if(opt==1) tag1(u,xx);
if(opt==2) tag2(u,xx);
}
else if(!(x>r||y<l) )
{
pushdown(u);
int mid=(l+r)>>1;
update(2*u,l,mid,x,y,xx,opt);
update(2*u+1,mid+1,r,x,y,xx,opt);
w[u]=max(w[2*u],w[2*u+1]);
}
}
int main()
{
int opt,x,y;
cin>>n>>q;
for(int i=1;i<=n;i++)
scanf("%ld",&a[i]);
build(1,1,n);
for(int i=1;i<=q;i++)
{
scanf("%d%d%d",&opt,&x,&y);
if(opt!=3)
{
int xx;
scanf("%d",&xx);
update(1,1,n,x,y,xx,opt);
}
else printf("%ld\n",query(1,1,n,x,y));
}
return 0;
}
```cpp