站外题求助(线段树)
  • 板块学术版
  • 楼主zhaoxibo
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/7/30 17:26
  • 上次更新2023/11/3 06:53:19
查看原帖
站外题求助(线段树)
592662
zhaoxibo楼主2023/7/30 17:26

题目大意是一个数列,三个操作, 11 是区间增加, 22 是区间赋值, 33 是区间查询,我打的是线段树,结果有WA有RE

#include<cstdio>
#define int long long
using namespace std;
int n,m;
long long d[200005<<2],b[200005<<2],b2[200005<<2];
void down2(int s,int t,int p){
	if(!b2[p]) return ;
	int mid=(s+t)>>1;
	d[p<<1]=(mid-s+1)*b2[p];b[p<<1]=0;b2[p<<1]=b2[p];
	d[p<<1|1]=(t-mid)*b2[p];b[p<<1|1]=0;b2[p<<1|1]=b2[p];
	b2[p]=0;
}
void down1(int s,int t,int p){
	if(b2[p]) down2(s,t,p);
	if(!b[p]) return ;
	int mid=(s+t)>>1;
	d[p<<1]+=(mid-s+1)*b[p];b[p<<1]+=b[p];
	d[p<<1|1]+=(t-mid)*b[p];b[p<<1|1]+=b[p];
	b[p]=0;
}
void update2(int l,int r,long long x,int s,int t,int p){
	if(l<=s&&t<=r){
		d[p]=(t-s+1)*x;
		b[p]=0;
		b2[p]=x;
		return ;
	}
	if((b[p]||b2[p])&&s!=t) down1(s,t,p);
	int mid=(s+t)>>1;
	if(l<=mid) update2(l,r,x,s,mid,p<<1);
	if(r>mid) update2(l,r,x,mid+1,t,p<<1|1);
	d[p]=d[p<<1]+d[p<<1|1]; 
}
void update1(int l,int r,long long x,int s,int t,int p){
	if(l<=s&&t<=r){
		if(b2[p]){
			d[p]=(t-s+1)*b2[p];
			down2(s,t,p);
		}
		d[p]+=(t-s+1)*x;
		b[p]+=x;
		return ;
	}
	if((b[p]||b2[p])&&s!=t) down1(s,t,p);
	int mid=(s+t)>>1;
	if(l<=mid) update1(l,r,x,s,mid,p<<1);
	if(r>mid) update1(l,r,x,mid+1,t,p<<1|1);
	d[p]=d[p<<1]+d[p<<1|1]; 
}
long long findth(int l,int r,int s,int t,int p){
	if(l<=s&&t<=r) return d[p];
	if((b[p]||b2[p])&&s!=t) down1(s,t,p);
	int mid=(s+t)>>1;
	long long sum=0;
	if(l<=mid) sum+=findth(l,r,s,mid,p<<1);
	if(r>mid) sum+=findth(l,r,mid+1,t,p<<1|1);
	return sum;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%lld",&x);
		update1(i,i,(long long)x,1,n,1);
	}
	for(int i=1;i<=m;i++){
		int A,B,C,D;
		scanf("%lld%lld%lld",&A,&B,&C);
		if(A!=3) scanf("%lld",&D);
		if(A==1) update1(B,C,(long long)D,1,n,1);
		else if(A==2) update2(B,C,(long long)D,1,n,1);
		else printf("%lld\n",findth(B,C,1,n,1));
	}
}

谢谢

2023/7/30 17:26
加载中...