Liyuqiao11 @ 2023-07-13 16:52:49
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
#define int long long
int n,m,a[N];
struct T{
int l;
int r;
int maxn;
int lazy;
int tag;
}t[N*4];
void pushup(int i){
t[i].maxn=max(t[i*2].maxn,t[i*2+1].maxn);
}
void pushdown(int i){
if(t[i].l==t[i].r){
t[i].lazy=-1e18;
t[i].tag=0;
return;
}
if(t[i].lazy!=-1e18){
t[i*2].lazy=t[i].lazy;
t[i*2].maxn=t[i].lazy;
t[i*2+1].lazy=t[i].lazy;
t[i*2+1].maxn=t[i].lazy;
t[i*2].tag=0;
t[i*2+1].tag=0;
t[i].lazy=-1e18;
return;
}
if(t[i].tag==0) return;
t[i*2].maxn+=t[i].tag;
t[i*2+1].maxn+=t[i].tag;
t[i*2].tag+=t[i].tag;
t[i*2+1].tag+=t[i].tag;
return;
}
void build(int i,int l,int r){
t[i].l=l;
t[i].r=r;
if(l==r){
t[i].maxn=a[l];
t[i].lazy=-1e18;
t[i].tag=0;
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
pushup(i);
}
void update(int i,int l,int r,int x){
if(t[i].l>=l&&t[i].r<=r){
t[i].lazy=x;
t[i].maxn=x;
t[i].tag=0;
return;
}
pushdown(i);
if(t[i*2].r>=l){
update(i*2,l,r,x);
}
if(t[i*2+1].l<=r){
update(i*2+1,l,r,x);
}
pushup(i);
}
void update_2(int i,int l,int r,int x){
if(t[i].l>=l&&t[i].r<=r){
t[i].tag+=x;
t[i].maxn+=x;
return;
}
pushdown(i);
if(t[i*2].r>=l){
update_2(i*2,l,r,x);
}
if(t[i*2+1].l<=r){
update_2(i*2+1,l,r,x);
}
pushup(i);
}
int query(int i,int l,int r){
if(t[i].l>=l&&t[i].r<=r){
return t[i].maxn;
}
pushdown(i);
int ans=-1e18;
if(t[i*2].r>=l){
ans=max(ans,query(i*2,l,r));
}
if(t[i*2+1].l<=r){
ans=max(ans,query(i*2+1,l,r));
}
return ans;
}
signed main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
for(int i=1;i<=m;i++){
int op,x,y,k;
cin>>op;
if(op==1){
cin>>x>>y>>k;
update(1,x,y,k);
}
else if(op==2){
cin>>x>>y>>k;
update_2(1,x,y,k);
}
else{
cin>>x>>y;
cout<<query(1,x,y)<<endl;
}
}
return 0;
}
by zhongshizhao1 @ 2023-08-07 20:54:39
首先建议你用“<<1”代替"2"并且用<<1|1代替2+1,能优化不少常数
by zhongshizhao1 @ 2023-08-07 20:55:08
2和2+1