题解：P12489 [集训队互测 2024] 线段树与区间加

· · 题解

好像发错号了。

为什么要过题才能发题解？

首先注意到 s_p 可以表示为 u 子树对应的值的和减去祖先的 lazy 之和乘上该区间的长度，所以其实只需要考虑如何维护 \sum lz_iv_i。

记 P_i 表示 [i,i] 对应节点。首先根据 zkw 线段树能够得到一个结论：线段树上区间 [l,r] 所包含的线段树区间，为 P_{l-1} 和 P_{r+1} 在树上构成的链内部的那部分。因此一次操作相当于将链上的点（实际上两端可以认为是 \operatorname{LCA}(P_{l-1},P_l) 和 \operatorname{LCA}(P_r,P_{r+1})）全都 pushdown，并且将这条链内侧第一层的所有点（类似一个毛毛虫的形状）全都加上 v。

因为 pushdown 之后的变化比较阴间，但是注意到如果我们考虑维护每个点到根的链上的 lazytag 之和，就会发现 pushdown 的时候等价于链上清空，而其他位置不会发生变化。

于是我们考虑在每个位置记录其到根的 lazytag 之和，这样当我们进行区间加的时候，实际上就等价于进行以下两个操作：

  1. 将一条链上所有的 a_i 改为 0；
  2. 将一条链内部所有点的 a_i 都加上 k；
  3. 查询 \sum (a_i-a_{f_i})v_i。

首先查询里面那个差分的系数可以也合并进 v_i 里，所以我们现在还是求 \sum a_iv_i。将链修改为 0 是简单的，现在我们的问题是对一条从下往上的链上所有点的不在链上的左/右子树进行操作。

考虑修改一下树剖的 dfs 序：对于一条重链，先从上到下依次遍历重链上的点，接着从下往上依次遍历链上的点的轻左子树（没有就跳过），最后从下往上依次遍历链上的点的轻右子树。

于是容易发现此时一条重链上的这些子树可以用上面的顺序中 O(1) 个区间来表示，于是这样我们就可以用 O(\log n) 个区间来表示一条任意的从下到上的链上的这些子树。

这样直接用一个普通的区间赋值区间加求带权和的线段树维护，总时间复杂度 O(n\log^2 n)。