求助,思路问题,不是查错
查看原帖
求助,思路问题,不是查错
240374
hicode_002楼主2021/7/21 16:49

求助,我的想法是不让乘法和加法出现在同一个节点,就是在向下修改和查询的时候,我在下放节点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;
}
2021/7/21 16:49
加载中...