hundunqidian @ 2022-07-30 10:32:16
提交后过了5个点,另5个点和样例都是RE 自查觉得应该是update2的问题 (将update2在主函数注释掉再提交,同样是过5个测试点,但剩余的都是WA了)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int const X=1e7+10;
ll ans[X<<2],tagj[X<<2],tagx[X<<2],a[X],n,m,x,y,kk,op;
bool gotx[X<<2];
//tagj:操作2,tagx:操作1,gotx:是否有操作1
inline ll ls(ll rt){
return rt<<1;
}
inline ll rs(ll rt){
return rt<<1 | 1;
}
void push_up(ll rt){
ans[rt]=max(ans[ls(rt)],ans[rs(rt)]);
return ;
}
void build(ll rt,ll L,ll R){
if(L==R){
ans[rt]=a[L];
return ;
}
ll mid=(L+R)>>1;
build(ls(rt),L,mid);
build(rs(rt),mid+1,R);
push_up(rt);
return ;
}
void f(ll rt,ll L,ll R,ll jia,ll gai,bool okx){
if(okx){ //有赋值
tagj[rt]=jia;
tagx[rt]=gai;
gotx[rt]=true;
ans[rt]=gai+jia;
}
else{//无赋值
tagj[rt]+=jia;
ans[rt]+=jia;
}
return ;
}
void push_down(ll rt,ll L,ll R){
ll mid=(L+R)>>1;
f(ls(rt),L,mid,tagj[rt],tagx[rt],gotx[rt]);
f(rs(rt),mid+1,R,tagj[rt],tagx[rt],gotx[rt]);
tagj[rt]=0; tagx[rt]=0; gotx[rt]=false;
return ;
}
void update1(ll rt,ll L,ll R,ll uL,ll uR,ll k){
//加法
if(uL<=L && R<=uR){
tagj[rt]+=k;
ans[rt]+=k;
return ;
}
ll mid=(L+R)>>1;
push_down(rt,L,R);
if(mid>=uL) update1(ls(rt),L,mid,uL,uR,k);
if(mid+1<=uR) update1(rs(rt),mid+1,R,uL,uR,k);
push_up(rt);
return ;
}
void update2(ll rt,ll L,ll R,ll uL,ll uR,ll k){
//赋值
if(uL<=L && R<=uR){
tagx[rt]=k; gotx[rt]=true;
tagj[rt]=0; ans[rt]=k;
return ;
}
push_down(rt,L,R);
ll mid=(L+R)>>1;
if(mid>=uL) update2(ls(rt),L,mid,uL,uR,k);
if(mid+1<=R) update2(rs(rt),mid+1,R,uL,uR,k);
push_up(rt);
return ;
}
ll query(ll rt,ll L,ll R,ll qL,ll qR){
if(qL<=L && R<=qR){
return ans[rt];
}
push_down(rt,L,R);
ll mid=(L+R)>>1,res=-1e18;
if(qL<=mid){
res=max(res,query(ls(rt),L,mid,qL,qR));
}
if(qR>=mid+1){
res=max(res,query(rs(rt),mid+1,R,qL,qR));
}
return res;
}
inline ll read(){
ll x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while('0'<=ch && ch<='9'){
x=x*10+(ch-48);
ch=getchar();
}
return x*f;
}
int main(){
n=read(); m=read();
for(ll i=1;i<=n;i++){
a[i]=read();
}
build(1,1,n);
while(m--){
op=read(); x=read(); y=read();
if(op==1){
kk=read();
update2(1,1,n,x,y,kk);
}
else if(op==2){
kk=read();
update1(1,1,n,x,y,kk);
}
else{
cout<<query(1,1,n,x,y)<<endl;
}
}
return 0;
}