结构：

• lazy_tag：

  为了方便（统一），区间修改只改tag，在pushdown时分成三步：

  • 计算当前节点信息
  • 下传tag
  • 清空当前节点tag

  另外，在查询和修改操作最前面pushdown。

  pushup时也要先pushdown子节点，保证子节点信息正确

• 关于lazytag的使用：2022/3/22改

  看情况。有时其实仍然是修改时保证父节点信息正确，有tag只表示下传并计算出子节点值更好。

应用：

• 加乘tag的下传计算 -> 算清楚就好了

• 区间加等差数列 -> 维护差分数组，前缀和单点查询

• 区间加平方数列 -> 高阶前缀和求

• 维护区间mex：F-little w and Discretization_牛客竞赛数据结构专题班树状数组、线段树练习题 (nowcoder.com)

  叶节点维护 ：数字 i 最后一次出现的位置（没出现过自然就是0）

  区间维护：一段区间最左边位置的点（即叶节点的最小值）

  对查询的区间离线，按 右端点 从小到大排序。

  query(pos) 表示查询第一个权值小于pos的叶节点编号，

  一个区间 [l,r] 的答案就是 query(q[i].l)，在查询一段区间时，如果左子树权值 >= pos，就说明 l~mid 的所有值全部在 pos 之后出现了，不可能成为mex值，因此就到右边去找。否则就可以在左子树中寻找。

• 维护区间历史最大值：（带区间修改+赋值）P4314 CPU 监控 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

  对于这种问题，由于我们的lazytag会在pushdown时进行修改，所以会导致难以将正确的历史最值更新到叶节点

  我们不对lazytag进行合并操作，想象成 一段操作序列（队列）。每次pushdown就把整段序列添加到左右儿子的队列尾，并清空当前节点的队列。

  显然这样可以根据队列的信息，计算出在哪个节点达到了最大值，即历史最值。

  但同时这样是不可行的，于是我们寻找一种方法：记录（维护）一个队列的标记对当前节点的影响

  即额外维护两个类似tag的信息：历史区间最大加和，历史区间最大赋值

  这样的话，在pushdown中进行详细的分类讨论，就可以解决这个问题。

• 线段树合并分裂应用于区间排序问题： P2824 [HEOI2016/TJOI2016]排序