顺颂 YFST 板子 & 使用例
题。首先树剖，然后变成在 \(\text{dfn}\) 区间上插一个关于 \(\text{dis}\) 的一次函数。这个很神奇，一般的李超树是，在 \(x\) 轴区间上插入关于 \(x\) 的一次函数。然而这里，\(\text{dfn}\) 与 \(\text{dis}\) 看起来毫无关系。
考虑李超树运用了线段的什么性质。无外乎，单调性和线性性。
第一个显然，你树剖出来的 \(\text{dfn}\) 连续段是一条链，\(\text{dis}\) 随 \(\text{dfn}\) 单调递增，那关于 \(\text{dis}\) 单调的函数自然也关于 \(\text{dfn}\) 单调。所以李超树维护的实际上是一堆折线。
有人就说，你只是在某些区间满足这个单调性，整棵树维护的东西不是乱套？管你吗的整棵树，修改查询的所有区间都合法就能满足我的要求，靠近根的那些点根本查不到。
对于线性性，它实际上是在满足这个：
if(f(ln)<g(now)(ln)) dnf(ls(now),ln,mid,f);
if(f(rn)<g(now)(rn)) dnf(rs(now),mid+1,rn,f);
就是说，如果线段 \(f\) 的两端点分别高于 \(g\)，那么 \(f\) 就没有任何一处的取值比 \(g\) 小。乍一看折线好像不行：
但是这里的折线不一般。注意到 \(\text{dfn}\) 到 \(\text{dis}\) 是一个映射，图中线段斜率 \(\text{dis}\times a\)（设关于 \(\text{dis}\) 函数的斜率是 \(a\)），那么如果折线 \(f\) 在某一处的斜率比 \(g\) 要大，\(f\) 所对应原函数的 \(a\) 也要更大，\(f\) 的斜率便永远大于 \(g\)，上图相交两次的情况根本不存在。
然后注意一次函数求值要把对应的 \(\text{dis}\) 而不是 \(\text{dfn}\) 代进去就是了。