题解 琴琴的树

· · 题解

可以看出链求和要差分吧。。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) 找区间有被卡常的风险。空间需要精细实现。其他应该还好。