主题

主题

 
   

Seg双标记的另外一种写法

感觉以前自己写的好丑,if比较多,常数有一点大。重新记录一下。

同样定义一个顺序。

之后我们的更新完全按照Update函数来更新,包括Pushdown。只不过是Pushdown按照标记的顺序而已。

Update函数里面,更新tag需要思考,更新信息似乎不太需要思考。

  • 例如维护“+”与“*”。

对于信息的维护,“+”与“*”都可以直接维护。

对于tag的维护,假设我们定义在Pushdown的时候先“*”在“+”。那么如果这次更新是“+w”,就直接把“+” 的tag+w。如果这一次更新是“*w”,就把“+”与“*”的tag都*w。

  • 再如维护“区间赋值”与“区间加”

对于信息的维护,同样可以直接维护。

对于tag的维护,假设我们定义在Pushdown的时候先计算“区间加”,在计算“区间赋值”。那么如果这一次更新是“区间赋值w”,就把“区间加”的标记清空,“区间赋值”的标记改为w。如果这一次更新是“区间加w”,就直接把“区间加”标记+w。

这玩意也可以反过来定义顺序。

对于tag的维护,假设我们定义在Pushdown的时候先计算“区间赋值”,在计算“区间加”。那么如果一次区间更新是“区间赋值w”,那么直接把“区间赋值”的标记改为w。如果这一次区间更新是“区间加w”,那么查看现在的标记——如果存在“区间赋值”标记,就把“区间赋值”标记+w,否则把“区间加”标记+w。

似乎上面二者较常见。之前写过几种。今天做题看见,于是又写了一下。

代码

 
 
评论