SegTree

很 educational 的题目。 可以看作是线段树的一种比较泛化的形式。 好的聚焦具体问题。 如果不强制在线，一个经典的做法是，对序列进行扫描线并维护时间轴。简直是天然的结构。 然后一个很本质的思考方向是，你在做线段树的时候，你其实在做一个合并。因为你要快速地查询单点的值，肯定是要通过某些压缩的结构来做到。 这个最大子段和的结构的合并是经典的。（都做这个题了应该会） 很明显的是这看起来比普通的区间修改单点查询强多了。因此考虑线段树。 我们发现我们可以把信息当成一个 Tag 来进行维护，每次询问就是 pushdown 到最底下然后看看 Tag。然后 Tag 之间是好合并的。 具体一点的话。考虑一个 Tag，他总是由两段组成，前一段是跟你初始的 a 有关，只可能是 ±a。而后一段都是常量。 因为每个地方的 a 不一样，我们可以分开维护。具体来讲对于第一段常量段我们只把 ±a 的符号提出来做最大子段和，容易知道乘上 ∣a∣ 后是对的。 每次 pushdown 其实就是把父亲的 Tag 接到儿子的后面。在接的时候如果前面的段有常量段了那后面的段的变量段也会变成常量。 注意 x 正负不同的时候因为取 max 所以形式是不同的，要都记一下。

看到子串出现类直接套上一个 SAM。 然后非常套路地使用线段树合并来维护子树的 endpos。 我们的限制即相当于是，给定一堆长度相等的线段（存在线段树里），然后要你算多少种方案插两根针不会把所有线段全部插到。 我们考虑正难则反，考虑多少种会把所有插到。 然后我们再转化，考虑一根针能插到的线段的起点位置是一个线段，即我们要选两个定长线段覆盖所有点。 这个问题简单多了，我们设第一个线段的末尾是 $x$，另一个的开头是 $y$。 我们先假设两个不是线段，我们假设要用 $[-\infin, x]$ 和 $[y,\infin]$ 来覆盖所有点。 二元限制我们画成图，容易发现满足条件的 $(x,y)$ 点对是一个右下角的，阶梯状面积，其中凹点在 $x=y$ 上，且凹点的 $x$ 就是点的位置。 然后我们考虑两个线段的限制，他其实就是给 $x$ 设定了一个上界，$y$ 设定了一个下界，然后这样合法的仍旧是一个阶梯状。 我们考虑在使用线段树维护阶梯状的时候，我们不从横坐标维护有多少个 $y$ 满足在当前 $x$ 下合法，我们维护那个突出去主对角线的面积。 你发现这个东西是好维护的，你对每个线段树节点维护第一个和最后一个点，然后 pushup 的时候算一下两边的贡献然后额外把少算的贡献算上即可。