线段树的一个输出问题
  • 板块学术版
  • 楼主pencil
  • 当前回复12
  • 已保存回复12
  • 发布时间2021/7/21 20:28
  • 上次更新2023/11/4 13:54:33
查看原帖
线段树的一个输出问题
137723
pencil楼主2021/7/21 20:28

期望shu函数输出队列,结果全是零

#include<bits/stdc++.h>
using namespace std;
int in[100100];
struct errer {
	int r,l,lz=0,sum=0;
} a[100100];
int read() {
	int zf=1,az=getchar(),zhi=0;
	if(az<='0'||az>='9') {
		if(az=='-')
			zf=-1;
		az=getchar();
	}

	while(az>='0'&&az<='9') {
		zhi=zhi*10+az-'0';
		az=getchar();
	}
	return zhi*zf;
}
void jian(int wz,int z,int y) {
	if(z==y) {
		a[wz].sum=in[z];
		return ;
	}
	a[wz].l=z;
	a[wz].r=y;
	int mid=(z+y)/2;
	jian(wz*2,z,mid);
	jian(wz*2+1,mid+1,y);
	a[wz].sum=a[wz*2].sum+a[wz*2+1].sum;
	return;
}
void tui(int wz) {
	if(!a[wz].lz) return;
	int mid=(a[wz].r-a[wz].l)/2;
	a[wz*2].lz+=a[wz].lz;
	a[wz*2].sum+=(mid-a[wz].l+1)*a[wz].lz;
	a[wz*2+1].lz+=a[wz].lz;
	a[wz*2+1].sum+=(a[wz].r-mid+2)*a[wz].lz;
	a[wz].lz=0;
}
void jia(int wz,int z,int y,int zhi) {
	if(a[wz].l<z||a[wz].r>y)
		return;
	if(a[wz].l>=z&&a[wz].r<=y) {
		a[wz].lz+=zhi;
		a[wz].sum+=(a[wz].r-a[wz].l+1)*a[wz].lz;
		return;
	}
	a[wz].lz+=zhi;
	tui(wz);
	int mid=(a[wz].l+a[wz].r)/2;
	if(z<=mid) jia(wz*2,z,mid,zhi);
	if(y>mid) jia(wz*2+1,mid+1,y,zhi);
	a[wz].sum=a[wz>>1].sum+a[wz>>1|1].sum;
}
int qiu(int wz,int z,int y) {
//	if(a[wz].r<z&&a[wz].l>y) return 0;
	if(a[wz].r>=z&&a[wz].l<=y) {
		return a[wz].sum;
	}
//	if(a[wz].l==a[wz].r)
//		return a[wz].sum;
	tui(wz);
	int mid=(a[wz].l+a[wz].r)/2,a1=0,b=0;
	if(z<=mid) a1=qiu(wz*2,z,mid);
	if(y>mid) b=qiu(wz*2+1,mid+1,y);
	return a1+b;
}
void shu(int wz){
	if(a[wz].l==a[wz].r){
		cout<<a[wz].sum<<" ";
		return ;
	}
	shu(wz>>1);shu(wz>>1|1);
}
int main() {
	int i,n,m,op=0;
	n=read();
	m=read();
	for(i=1; i<=n; i++)
		in[i]=read();
	jian(1,1,n);
	for(i=1; i<=m; i++) {
		op=read();
		int x=read(),y=read(),z;
		if(op==1) {
			z=read();
			jia(1,x,y,z);
			cout<<endl;
			shu(1);
			cout<<endl;
		}
		if(op==2) {
			cout<<qiu(1,x,y)<<endl;
		}
	}
	return 0;
}
2021/7/21 20:28
加载中...