吉司机线段树

发布时间 2023-03-24 20:34:44作者: Diamondan

1.对于所有的i∈[l,r],将Ai加上 k(k 可以为负数)

  对于k的值,我们分类讨论,讨论其对区间最大值的影响
  	1)k==0 无影响
  	2)k<0 正常加上即可
        3) k>0,只有这种情况可能会对最大值结果产生影响

  我们考虑用 Tag1 来维护,显然当 Tag1 累计到最大后,下传给 son
  区间 son 的最大值加上对应 Tag[1] ,才可能可以使 son 的 mx 最大,才有可能更新为历史最大
  再用一个 Tag2 维护先前出现的【最大的 Tag1 】,以便更新B数组
  总结一下:
  tag 大致上可以分成2类:
  	1.区间累加标记  2.历史区间最大累加标记
  再考虑区间内最大值与非最大值之间的关系可能发生转换,
  tag 又可以分成:
  	1.区间最大累加值的标记 2.区间非最大值的累加标记
  具体就有了 Summary 中的4种 Lzay_tag

*2.对于所有的i∈[l,r],将Ai变成 min(Ai,v)

  我们考虑维护线段树对应节点的:区间最大值mx、严格次大值se、最大值的个数cnt
  if(v>=mx) 不用修改
  if(se<v<mx) 区间和 sum-=(mx-v)*cnt ,mx更新为v,打上区间最大值加减标记
  if(x<=se) 不能直接更新,对lson与rson进行递归搜索,结果合并到当前节点

3.求 ∑i=[l,r]Ai

  线段树基操,省略

4.对于所有的i∈[l,r],求Ai的最大值 & 5.对于所有的i∈[l,r]求Bi的最大值

  其中最为区间历史最大值的 Bi 较为难求,采用Lzay_tag的方式维护,维护方式见1与2

Summary:
总共要维护的是四个Lazy_tag

  1.区间历史最大累计和的tag
  2.区间非最大值的历史最大累计和的tag
  3.区间最大值累加的tag
  4.区间非最大值的累加的tag