求助区间加历史和线段树
  • 板块学术版
  • 楼主DengDuck鄧德
  • 当前回复15
  • 已保存回复16
  • 发布时间2024/8/29 17:17
  • 上次更新2024/8/29 20:33:12
查看原帖
求助区间加历史和线段树
501947
DengDuck鄧德楼主2024/8/29 17:17

我应该怎么写 Down ?怎么维护标记?

自己想到的写法是

inline void Down(int u,int L,int R)
{
	if(t[u].Lz)
	{
		t[Ls(u)].S+=t[u].Lz*(Mid-L+1),t[Rs(u)].S+=t[u].Lz*(R-Mid);
		t[Ls(u)].Lz+=t[u].Lz,t[Rs(u)].Lz+=t[u].Lz;
		t[u].Lz=0;
	}
	if(t[u].Tim)
	{
		PushTim(Ls(u),t[u].Tim),PushTim(Rs(u),t[u].Tim);
		t[u].Tim=0;
	}
}

但是问题是啥呢,问题是 Upd 应该这么写对吧

void Upd(int u,int L,int R,int l,int r,LL x)
{
	if(R<l||r<L)return;
	if(l<=L&&R<=r)
	{
		t[u].Lz+=x,t[u].S+=x*(R-L+1);//注意这里
		return;
	}
	Down(u,L,R);
	Upd(Ls(u),L,Mid,l,r,x),Upd(Rs(u),Mid+1,R,l,r,x);
	Up(u);
}

那如果我不同的时间轴两次区间加,标记被合并了是不是就错完了。

如果错完了,我改咋写啊。

2024/8/29 17:17
加载中...