历史和 & 最值操作
线段树维护历史和
一些线段树的重点在于标记的下传，而非合并区间。在 push_down 时，两个 tag 的复合顺序是先儿子 tag 后父亲 tag。一个 tag 需要完整的记录它能将子区间变成什么样，并且支持下传时快速复合到子区间 tag，同时更新答案。因此，这样广义的 tag 可以支持很多奇怪的操作。
大魔法师是一道典题，也可以看作是历史和，可以帮助你理解 tag 下传时复合的顺序。但是我不想再 paste 一遍了，所以自己去右上角搜吧。
P8868 [NOIP2022] 比赛
给定两个长为 \(n\) 的排列 \(p,q\)，多次询问，每次询问给定区间 \([l,r]\)，问 \([l,r]\) 的所有子区间 \([x,y]\) 的 \(\min\{p_i\}\times \min\{q_i\}\) 之和是多少。
注意到信息不好直接维护，考虑扫描区间右端点，通过两个单调栈和线段树动态维护每个左端点对应的区间最小值 \(x_i,y_i\)，线段树用来支持对 \(x_i,y_i\) 的区间推平。
考虑如何查询答案，我们希望维护一个数组 \(s\)，并让线段树支持操作 \(s_i\gets s_i+x_iy_i\)。尝试设计一个 tag，支持上面三种操作。由于会发生区间推平，我们需要记录区间推平之前 \(x,y\) 序列对 \(s\) 的贡献，才能让子区间知道如何计算贡献（又由于 \(x,y\) 可能不被同时推平，因此需要记录一个被推平而另一个不被推平的贡献）。设 \(tag[p]=(a,b,c,d,tx,ty)\) 表示，依次执行：
- \(s_i\gets s_i+ax_iy_i+bx_i+cy_i+d\)
- 若 \(tx>0\)，\(x_i\gets tx\)
- 若 \(ty>0\)，\(y_i\gets ty\)
同时我们在线段树中维护 \((sxy,sx,sy,ss)\) 表示 \(\sum x_iy_i,\sum x_i,\sum y_i,\sum s_i\)。尝试将 \(tag[p']=(a',b',c',d',tx',ty')\) 复合到标记 \(tag[p]=(a,b,c,d,tx,ty)\) 和信息 \((sxy,sx,sy,ss)\) 上：
分讨是否存在 tx,ty 标记，执行对应的操作：
tx ty op
0 0 a += a' s += a * sxy + b * sx + c * sy + d * len
0 ty b += a' * ty s += a * sx * ty + b * sx + c * ty * len + d * len
tx 0 c += a' * tx s += a * tx * sy + b * tx * len + c * sy + d * len
tx ty d += a' * tx * ty s += a * tx * ty * len + b * tx * len + c * ty * len + d * len
0 b += b'
tx d += b' * tx
0 c += c'
ty d += c' * ty
d += d'
还要根据 tx',ty' 立即更新自己的 sx,sy,sxy，基本思路也同上，此处不展开了
总之，对于一个大区间 \(p\) 和它的 tag，我们不仅要知道 \(p\) 当前的答案是多少；随便选一个儿子 \(p'\)，我们还能用 tag 立即将 \(p'\) 的答案和 tag 更新到当前状态。
P8528 [Ynoi2003] 铃原露露
先用支配对转化成二维问题，这里讲如何维护。问题等价于：给你一些 3-side 矩形，每次查询一个 2-side 矩形内有多少空白面积。
我们对纵坐标扫描线，维护 \(0\) 出现次数的历史和。由于在接受标记的过程中，一个区间不会向下递归，因此其 mnc 不会改变。用 tag 记录有多少次统计更新历史和的时候，当前区间的最小值为 \(0\)，记为 tb。那么下传时仿照线段树 3 判一下儿子的最小值是不是和自己一样，然后儿子的答案会增大 \(mnc[p']\times cnt\)。
可以检查 pushdown 后立即 pushup，原区间的信息会不会改变（显然不能改变）。这个性质是显然的，对所有带标记的树都必须成立（如果你按我的写法的话。一边 move_tag 一边更新答案，这样查询时就不用 push_down 了对吧）。
最值操作
吉司机线段树，就是记一下最大值次大值，然后如果取 \(\min\) 的时候不会影响到次大值（最大值合并到次大值也算影响），就直接返回，否则递归向下。据说有一些势能分析，保证没有区间加的时候是单 \(\log\)，有区间加的时候是双 \(\log\)。
咕咕咕。