自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 22:34:53，当前版本为作者最后更新于2021-10-28 21:46:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可以看出链求和要差分吧。。$x,y$ 的 LCA 就是两区间去掉前导 $0$ 的 LCP。

先对 $x,y$ 去掉前导 $0$。

然后到根的和就是区间的每个前缀对应的结点的和。

不过维护区间和结点的对应关系过于复杂，所以我们直接维护区间即可。即实质上的，对于一个结点加，其实是把序列上所有等价于这个结点的区间加。

子树加的话首先要找到 $x$ 在序列上所有相同的区间。SA 的话要找到所有 $lcp(l_x,y)\ge r_x-l_x+1$ 的后缀 $y$。这个显然是在 height 数组上的一个区间。

有两个线性空间的做法：height 数组线性空间，$O(\log n)$ 时间的 $O(n)-O(1)$ RMQ 上二分或者线段树二分，和离线排序，每次加入所有 $\ge r_x-l_x+1$ 的 $height_i$，然后用并查集维护连续段（这个做法可以用线性树上并查集优化到线性时间，不过不是瓶颈，所以不重要）。

其实每个后缀的所有非 $0$ 前缀都组成了一条从根往下的链。所以对每个后缀进行操作，就是将这个后缀的所有长度 $\ge r_x-l_x+1$ 的前缀加。

看做二维平面，将每个后缀平移到同样的位置（或者说是每个后缀的前缀从都从 $1$ 开始编号），那么就是一个矩形加。

设二分出的区间为 $L,R$，二维平面为 $a_{x,y}$，那么就是 $\forall x\in [L,R],y\in [r_x-l_x+1,n],a_{x,y}$ 加上 $v$。

至于链求和，就是求这个后缀所有长度 $\le r-l+1$ 的前缀的和。设这个区间为 $[l,r]$，那么就是求 $\sum_{i=1}^{r-l+1} a_{rk_l,i}$。

这个 CDQ+树状数组，随便拆一下贡献即可，$O(n\log ^2n)$ 时间，线性空间。

代码可以找我要。

常数的话，线段树 $O(n\log^2 n)$ 找区间有被卡常的风险。空间需要精细实现。其他应该还好。