线段树进阶

多信息合并

\(\text{GSS3 Solution}\)

\(\text{link}\)

对于线段树的每个结点，记录其区间和（\(sum\)），区间前后缀最大子段和（\(lmax,rmax\)）和区间最大子段和（\(vmax\)）。

合并：

\[vmax=\max\{vmax_{lson},vmax_{rson},rmax_{lson}+lmax_{rson}\}
\]

\[lmax=\max\{lmax_{lson},sum_{lson}+lmax_{rson}\}
\]

\(rmax\) 转移与 \(lmax\) 类似。

显然支持单点修改。

复杂度 \(O(n\log n)\)。

\(\text{P4247 Solution}\)

\(\text{link}\)

其实是一道数学题。

注意到 \(c\) 很小，可以在线段树上的每个结点记录 \(c=1,2,...,20\) 的值。

合并即为

\[c_i=\sum_{j=0}^ic_{lson,j}c_{rson,i-j}
\]

区间乘 \(-1\) 只需将 \(i\) 为奇数的 \(c_i\) 变为相反数即可。

区间加比较麻烦，将式子变为括号乘起来的形式再拆，可以得到

\[c_i={\sum_{j=0}^{i-1}}c_j\cdot C_{len-j}^{i-j}\cdot x^{i-j}
\]

其中 \(C\) 为组合数，\(x\) 为增量，\(len\) 为当前结点代表区间的长度。

组合数可以预处理，维护一下 \(c\) 即可。

复杂度 \(O(400n\log n)\)。

线段树二分

在具有某种单调性的线段树上查找某个值，如果朴素二分 + 线段树区间查询，复杂度为 \(O(\log^2n)\)，线段树是天然的分治结构，当二分到某个结点时直接判断出答案在左儿子还是右儿子就可以做到 \(O(\log n)\)。

\(\text{CF992E Solution}\)

\(\text{link}\)

似乎不太好统计，观察性质，发现 \(a\) 非负，所以 \(s\) 单调不降，定义新的数组 \(b\) 为 \(s_{i-1}-a_i\)，操作变为区间加，查询 \(b\) 中是否存在 \(0\)。

注意到对于 \(b\) 非负的位置，此时 \(s\) 至少翻倍，而翻倍 \(O(\log10^9)\) 此后必大于 \(10^9\)，也就是以后的 \(b\) 都为负。

所以至多有 \(O(\log10^9)\) 个 \(b\) 的值是我们需要的，二分查找即可。

复杂度 \(O(n\log n\log10^9)\)。

均摊复杂度的线段树

找不到原题了。

一个序列 \(A\)，支持区间开平方根，查询区间和。

开平方根很难维护，然而我们知道 \(0\) 和 \(1\) 开平方根后还是它本身，而且一个数只需要很少次开平方根就可以变为 \(1\)。

这启发我们在区间开平方根时，如果区间最大值小于等于 \(1\)，直接跳过，否则暴力递归。由上面的性质，可以证明复杂度为 \(O(kn\log n)\)，\(k\) 是一个较小的常数。

线段树优化 dp

\(\text{P2565 Solution}\)

\(\text{link}\)

令 \(f_{i,j}\) 表示在前 \(i\) 个村庄中建立 \(j\) 个基站所花费的最小代价， \(i\) 必选，那么就有一个朴素的转移式 \(f_{i,j}=\min_{z=0}^{i-1}\{f_{z,j-1}+sum(z,i)\}+w_i\)，\(sum(l,r)\) 为在 \(l\) 和 \(r\) 设立基站的情况下 \(l\) 到 \(r\) 所有基站的补偿值，然而这样做复杂度 \(O(n^3+n^2k)\)，无法接受。

发现复杂度瓶颈在于 \(sum(l,r)\) 的计算，对于每一个村庄，在当前枚举村庄与它的距离大于它的接收半径的时候将它左侧超出它接收半径的村庄的 \(f\) 值加上 \(c\)，这样就转化为了一个区间加，区间最小值的操作，使用线段树实现。

复杂度 \(O(nk\log n)\)。

线段树分治

对于维护支持加，撤销但不支持删除操作的数据结构时，可以用线段树分治的方式，对时间轴建立线段树，把一个在 \(s\) 时刻加入，\(t\) 时刻删除的操作转化为在 \([s,t)\) 时间段加入的操作，再通过线段树让加入的操作总量在 \(O(q\log n)\)。

统计答案时先序遍历整棵线段树，依次加入当前节点的所有操作，然后遍历左右儿子，然后撤销当前节点的操作，返回，在叶子节点统计答案。

\(\text{P5787 Solution}\)

\(\text{link}\)

判断一个图是否为二分图可以用染色法，具体的，若存在边 \((x,y)\) 说明 \(x,y\) 一黑一白，采用并查集来维护即可，因为有删除操作，把整个过程用线段树分治，并查集需要撤销，所以不能路径压缩。

复杂度 \(O(n\log^2n)\)。

\(\text{CF576E Solution}\)

\(\text{link}\)

注意到 \(k\) 很小，判断是否为二分图依然可以采用可撤销并查集的方法，但这里有一个问题，操作的是否执行取决于前面的状态，这就不能使用平凡的线段树分治，考虑将一个存在时间为 \([l,r]\) 的边拆成存在时间为 \([l,l]\) 和 \([l+1,r]\) 的边，显然 \([l,l]\) 这个区间会先遍历到，这时，如果是二分图，不用修改，否则，将 \([l+1,r]\) 对应的边删除贡献即可（将它的颜色改为上一次操作的颜色）。

注意一下空间大小，最好使用 std::stack 存储撤销操作。

复杂度 \(O(n\log^2n)\)。

特殊合并

当不能直接 \(O(1)\) 更新线段树上父亲（push_up）时通过记录附加信息+二分 \(O(\log n)\) 完成更新。

\(\text{P9130 Solution}\)

\(\text{link}\)

注意到值域那么大没用，直接离散化，接下来只需考虑值域为 \(n\) 时的情形。

令树上的结点存 \(x\)，结点对应的区间多少天没有干草吃，\(y\)，结点对应的区间的干草超出右端点多少天，\(v\)，有干草吃的天数和（即答案）。

考虑合并两个结点，\(x\) 和 \(y\) 的合并是显然的，重点在于 \(v\) 的合并，左儿子所贡献的 \(v\) 显然不会被右儿子影响，只需考虑左儿子的 \(y\) 对右儿子的贡献即可。

进行一个分的讨，将右儿子分成两部分 \(ls,rs\)，记左儿子的 \(y\) 为 \(Y\)，若 \(Y \ge ls_x\)，显然 \(ls\) 的区间会被全部覆盖，令 \(Y\gets Y-ls_x+ls_y\)，然后递归计算 \(rs\)，否则 \(rs\) 对 \(v\) 的贡献不变（为右儿子的 \(v-ls_v\)），递归计算 \(ls\) 的贡献。