我应该怎么写 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);
}
那如果我不同的时间轴两次区间加,标记被合并了是不是就错完了。
如果错完了,我改咋写啊。