关于权值线段树区间加
  • 板块学术版
  • 楼主ShunpowerSHUN理成张
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/3/5 17:23
  • 上次更新2023/10/28 07:13:33
查看原帖
关于权值线段树区间加
399150
ShunpowerSHUN理成张楼主2022/3/5 17:23

经过一下午缝合普通线段树与权值线段树,以及教练对于 pushdown 的指导,写了一个很奇怪的东西:

void pushdown(int p,int l,int r){
	int m=(l+r)>>1; 
	t[lson[p]]+=t[p];
	k[lson[p]]+=(m-l+1)*t[p];
	t[rson[p]]+=t[p];
	k[rson[p]]+=(r-m)*t[p];
	t[p]=0;
}
void modify(int &p,int l,int r,int ml,int mr,int v){
	if(!p){
		tnt++;
		p=tnt;
	}
	if(ml<=l&&r<=mr){
		k[p]+=v*(r-l+1);
		t[p]+=v;
		cout<<k[p]<<","<<t[p]<<","<<l<<","<<r<<endl;
		return;
	}
	int m=(l+r)/2;
	if(!lson[p]){
		tnt++;
		lson[p]=tnt;
	}
	if(!rson[p]){
		tnt++;
		rson[p]=tnt;
	}  
	pushdown(p,l,r);
	if(ml<=m){
		modify(lson[p],l,m,ml,mr,v);
	}
	if(mr>m){
		modify(rson[p],m+1,r,ml,mr,v);
	}
	k[p]=k[lson[p]]+k[rson[p]];
}

tt 是懒标记,kk 是值。

请各路聚聚帮我看看哪里死了,现在的问题是修改不对(而且不是完全不对,整体是对的但是整体更小的区间就死了,比如 [1,10][1,10] 的更新是对的但是 [1,5][1,5][6,10][6,10] 都死了)

2022/3/5 17:23
加载中...