theking_tiaoyange @ 2022-07-12 11:35:19
#include<cstdio>
#include<algorithm>
#define ll long long
#define N 1000005
using namespace std;
int n,q,t,x,y,k;
struct Node {
ll s,layc,laya;
bool fc;
}tree[N<<2];
void PushUp (int u) {
tree[u].s=max(tree[u<<1].s,tree[u<<1|1].s);
}
void Build (int l,int r,int u) {
if(l==r){
scanf("%lld",&tree[u].s);
return;
}
int m=l+r>>1;
Build(l,m,u<<1);
Build(m+1,r,u<<1|1);
PushUp(u);
}
void PushDown (int l,int r,int u) {
if(l==r)return;
if(tree[u].fc){
tree[u<<1].layc=tree[u<<1|1].layc=tree[u].layc;
tree[u<<1].laya=tree[u<<1|1].laya=tree[u].laya;
tree[u<<1].fc=tree[u<<1|1].fc=1;
tree[u<<1].s=tree[u<<1|1].s=tree[u].s;
}
else{
tree[u<<1].s+=tree[u].laya;
tree[u<<1|1].s+=tree[u].laya;
tree[u<<1].laya+=tree[u].laya;
tree[u<<1|1].laya+=tree[u].laya;
}
tree[u].laya=tree[u].fc=0;
}
void Update1 (int L,int R,int l,int r,ll x,int u) {
if(l>=L&&r<=R){
tree[u].s=x;
tree[u].layc=x;
tree[u].fc=1;
tree[u].laya=0;
return;
}
PushDown(l,r,u);
int m=l+r>>1;
if(m>=L)Update1(L,R,l,m,x,u<<1);
if(m<R)Update1(L,R,m+1,r,x,u<<1|1);
PushUp(u);
}
void Update2 (int L,int R,int l,int r,ll x,int u) {
if(l>=L&&r<=R){
tree[u].s+=x;
tree[u].laya+=x;
return;
}
PushDown(l,r,u);
int m=l+r>>1;
if(m>=L)Update2(L,R,l,m,x,u<<1);
if(m<R)Update2(L,R,m+1,r,x,u<<1|1);
PushUp(u);
}
ll Query (int L,int R,int l,int r,int u) {
if(l>=L&&r<=R)return tree[u].s;
PushDown(l,r,u);
int m=l+r>>1;ll ans=-1ll*1e16;
if(m>=L)ans=max(ans,Query(L,R,l,m,u<<1));
if(m<R)ans=max(ans,Query(L,R,m+1,r,u<<1|1));
return ans;
}
int main () {
scanf("%d%d",&n,&q);
Build(1,n,1);
while(q--){
scanf("%d",&t);
if(t==1){
scanf("%d%d%lld",&x,&y,&k);
Update1(x,y,1,n,k,1);
}
else if(t==2){
scanf("%d%d%lld",&x,&y,&k);
Update2(x,y,1,n,k,1);
}
else{
scanf("%d%d",&x,&y);
printf("%lld\n",Query(x,y,1,n,1));
}
}
return 0;
}
by 凤年 @ 2022-07-21 09:53:01
void PushDown (int l,int r,int u) {
if(l==r)return;
可以将这里的判断去掉试试,如果还是MLE就开大一倍数组