势能分析
1.基础数据结构练习题
判断区间中的数是否都相等，相等就可以打标记，特殊情况是 $x^2,x^2-1$，特判即可。
2.「雅礼集训 2017 Day1」市场
判断区间的数除 $d$ 的差值是否相等即可。
定义势能为 $\sum \lg |a_i-a_{i-1}|$。
区间最值操作
板子
1.Gorgeous Sequence
给你一个序列，支持区间取 $min$，查询区间最大值，查询区间和。
考虑维护 $mx,cnt,se$ 分别代表区间最大值，区间最大值的个数，区间次大值。
区间对 $x$ 取 $min$ 时，分讨一下：
$mx \le x$ 时，无需操作。
$se < x < mx$ 时，此时可以 $O(1)$ 更新信息，打个标记即可。
$x \le se$ 时，暴力递归子节点。
时间复杂度为 $O(mlogn)$。
证明
记每个节点的标记为 $mx$，并将与父亲节点标记相同的删去。
这样每个节点的次大值为其子树（不包含该节点）的标记的最大值。
定义一类标记为一次修改及懒标记下传得到的标记，记一类标记的权值为子树中包含该标记的节点数量，记势能函数 $\Phi(x)$ 为所有标记的权值和。
将区间取 $min$ 操作分为两种：常规操作与暴力递归。
常规操作复杂度肯定是对的。
每次暴力递归相当于回收标记，每次遍历到一个节点则子树中一定会有一个标记被回收，即 $\Phi(x)$ 减 $1$。
势能总和是 $O((n+m)\log n)$ 级别的，所以总时间复杂度为 $O((n+m)\log n)$。
实现时可以将取 $\min$ 标记换为 $mx$，也是对的。
2.Pick loves segment tree
给你一个序列，支持区间取 $min$，区间加减，区间求和。
加入区间加减后，上述信息仍可维护，直接套用即可。
重点是时间复杂度。
修改势能函数的定义：记 $\Phi(x)$ 为每个标记的深度和。
每次区间加减相当于增加 $O(logn)$ 个标记，那么 $\Phi(x)$ 增加 $O(log^2n)$。
每次暴力递归均摊就是每遍历一个节点 $\Phi(x)$ 减少 $1$。
这样时间复杂度为 $O((n+m)\log^2n)$。
实际时间复杂度接近单 $\log$。
3.最假女选手
给你一个序列，支持区间加减，区间取 $\max \& \min$，查询区间和，区间 $\max \& \min$。
划分数域
1.Mzl loves segment tree
给你一个序列，支持区间取 $\min \& \max$，区间加减，查询区间历史变动次数。
划分数域，将数拆为：最大值、最小值、其他。
发现区间取 $\min/\max$ 相当于对于最大值最小值的区间加减。
下传标记时顺便更新历史变动次数即可。
2.ChiTuShaoNian loves segment tree
给你两个序列 $a,b$，支持对 $a,b$ 区间取 $\min$，区间加，查询区间 $a+b$ 的最大值。
划分数域，分为同时为 $a,b$ 最大值的，只 $a$ 不 $b$ 的，…，四类。分别维护标记、答案。
时间复杂度 $O((n+m)\log^2n)$。
对于 $k$ 个序列的，可以做到 $O(2^k(n+m)\log^2n)$。
6.Dzy loves segment tree
给你一个序列，支持区间取 $\min$，区间加减，查询区间 $\gcd$。
将最大值和其他值分开维护，其他值进行差分。
合并时对于差分的 $\gcd$ 区间拼接的顺序是不重要的。
历史问题
将每次操作后得到的序列（或其他）视为一个新版本，那么历史问题就是针对历史版本的询问。主要有：历史最大/最小值，历史和。
1.CPU 监控
可以用懒标记实现。
最原始的，将标记看作一个队列，但是不能直接维护这个队列。
考虑化简为 $atag+ctag$
也可以矩阵，用 $(+,\max)$ 广义矩阵乘法。
每个节点维护 $\begin{bmatrix} his \\ a \\ 0 \end{bmatrix}$。
区间加 $k$ 的标记矩阵为：
区间赋值为 $k$ 的标记矩阵为：
矩阵满足结合律，这样就不用考虑标记的合并了。
缺点是常数太大，可以拆矩阵优化。
2.【清华集训2015】V
标记形如 $(a,b)$ 表示 $x \gets \max(x+a,b)$。
标记的合并即为 $(a,b)+(c,d)=(a+c,\max(b+c,d))$。
考虑历史标记最大值的合并 $(a,b)+(c,d)=(\max(a,c),\max(b,d))$，可以画图理解。
3.Rikka with Sequences
给你一个的序列 $a$，记 $b_{l,r}=\sum_{i=l}^{r}a_i$，对 $a$ 单点修改，对 $b$ 单点查询，每次操作后会更新 $b_{l,r}=\min(b_{l,r},\sum_{i=l}^{r}a_i)$。
相当于二维平面上区间加，单点查询历史最小值，用 KDT 维护，时间复杂度 $O(m\sqrt{n})$。
4.【模板】线段树 3
将最大值和非最大值分开维护。
下方标记时，最大值来自哪个节点，最大值的标记就下方到哪个节点。
5.[NOIP2022] 比赛
扫描线，转化为区间历史和问题。
每次线段树二分找到要区间覆盖的区间。
需要维护$his,\sum ab,\sum a,\sum b$，用矩阵实现。
具体转移矩阵就不写了。
直接做过不去，拆矩阵即可。
具体做法就是输个大样例，看哪个位置不为 $0$，然后预处理矩阵乘法，都写下来。
应该不卡常，我多维护了 $2$ 个信息还跑的挺快的。
杂题
1.Julia the snail
扫描线，这是经典的吉司机线段树。
参考
2016 年 jry 的集训队论文