求助,我的想法是不让乘法和加法出现在同一个节点,就是在向下修改和查询的时候,我在下放节点o之前先下放节点o的左儿子标记和右儿子标记,然后再下放节点o,这样加法和乘法不就不会撞了,不用管优先级
当到达边界时,在修改或返回答案之前先下放已有的标记。
这样却只有30分 求救,谢谢
大佬解释一下原因
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
ll sumv[400010],lazytagadd[400010],lazytagmul[400010],a[100010];
const int p=571373;
inline void pushup(const int&o){
sumv[o]=(sumv[o<<1]%p+sumv[o<<1|1]%p)%p;
}
inline void build(const int&o,const int&l,const int&r){
lazytagadd[o]=0;
lazytagmul[o]=1;
if(l==r){
sumv[o]=a[l]%p;
return;
}
int mid=(l+r)>>1;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
pushup(o);
}
inline void pushdown(const int&o,const int&l,const int&r){
if(l==r){
lazytagadd[o]=0;
lazytagmul[o]=1;
return;
}
int mid=(l+r)>>1;
sumv[o<<1]=(sumv[o<<1]%p+(lazytagadd[o]%p*((mid-l+1)%p))%p)%p;
sumv[o<<1|1]=(sumv[o<<1|1]%p+((lazytagadd[o]%p)*((r-mid)%p))%p)%p;
lazytagadd[o<<1]=(lazytagadd[o<<1]%p+lazytagadd[o]%p)%p;
lazytagadd[o<<1|1]=(lazytagadd[o<<1|1]%p+lazytagadd[o]%p)%p;
lazytagadd[o]=0;
sumv[o<<1]=(sumv[o<<1]%p*(lazytagmul[o]%p))%p;
sumv[o<<1|1]=(sumv[o<<1|1]%p*(lazytagmul[o]%p))%p;
lazytagmul[o<<1]=(lazytagmul[o<<1]%p*(lazytagmul[o]%p))%p;
lazytagmul[o<<1|1]=(lazytagmul[o<<1|1]%p*(lazytagmul[o]%p))%p;
lazytagmul[o]=1;
}
inline void change(const int&o,const int&l,const int&r,const int&ql,const int&qr,const ll&v,const int&mode){
if(ql<=l&&qr>=r){
if(mode){
pushdown(o,l,r);
lazytagadd[o]=(lazytagadd[o]%p+v%p)%p;
sumv[o]=(sumv[o]%p+v%p*((r-l+1)%p)%p)%p;
// pushdown(o,l,r);
return;
}else{
pushdown(o,l,r);
lazytagmul[o]=(lazytagmul[o]%p*(v%p))%p;
sumv[o]=(sumv[o]%p*(v%p))%p;
// pushdown(o,l,r);
return;
}
}
int mid=(l+r)>> 1;
pushdown(o<<1,l,mid);
pushdown(o<<1|1,mid+1,r);
pushdown(o,l,r);
if(ql<=mid){
change(o<<1,l,mid,ql,qr,v,mode);
}
if(qr>mid){
change(o<<1|1,mid+1,r,ql,qr,v,mode);
}
pushup(o);
}
inline ll querys(const int&o,const int&l,const int&r,const int&ql,const int&qr){
if(ql<=l&&qr>=r){
pushdown(o,l,r);
return sumv[o]%p;
}
int mid=(l+r)>>1;
pushdown(o<<1,l,mid);
pushdown(o<<1|1,mid+1,r);
pushdown(o,l,r);
ll ans=0;
if(ql<=mid){
ans+=querys(o<<1,l,mid,ql,qr)%p;
}
if(qr>mid)ans+=querys(o<<1|1,mid+1,r,ql,qr)%p;
return ans%p;
}
int main(){
memset(sumv,0,sizeof sumv);
int n,m;
cin>>n>>m;
cin>>a[1];
if(!m)return 0;
for(int i=1;i<=n;++i)cin>>a[i];
build(1,1,n);
while(m--){
int opt;
cin>>opt;
if(opt==1){
int x,y;
ll k;
cin>>x>>y>>k;
change(1,1,n,x,y,k,0);
}else if(opt==2){
int x,y;
ll k;
cin>>x>>y>>k;
change(1,1,n,x,y,k,1);
}else{
int x,y;
cin>>x>>y;
cout<<querys(1,1,n,x,y)%p<<endl;
}
}
return 0;
}