Lnk。这是一个 dfs 序 + 主席树的乱搞做法。
首先把树上距离拆开，令 \(\operatorname{dis}(u)\) 表示 \(u\) 到根的路径长度：
\[\left(\sum_{i=l}^r \operatorname{dis}(p_i)\right)+\left(\sum_{i=l}^r \operatorname{dis}(x)\right)-2\sum_{i=l}^r \operatorname{dis}(\operatorname{lca}(p_i,x)) \]前两项做个前缀和即可简单维护。考虑第三项。
用树剖可以转化成：\(p_i\) 到根的路径加与 \(u\) 到根的路径查询，参考这题或其他题解。在线的话，可持久化一下即可。不优之处在于，树剖会把路径剖成 \(\log\) 个区间，每个版本修改 \(\log\) 次，空间复杂度是 \(\Theta(n\log^2 n)\) 的。
考虑转化成序列问题。首先还是用可持久化数据结构，将 \(p_{1,\cdots,v}\) 插到版本 \(v\) 中，区间询问做差分；\(\operatorname{swap}(p_x,p_{x+1})\) 只对版本 \(x\) 有影响，将 \(p_x\) 删除，\(p_{x+1}\) 插入即可。
使用欧拉序可以把 \(\operatorname{lca}\) 转化成 \(\operatorname{rmq}\)。记 \(\operatorname{rmq}(l,r)\) 表示欧拉序上 \([l,r]\) 中，深度 \(\operatorname{dep}\) 最小的结点，\(\operatorname{lst}_u\) 表示结点 \(u\) 在欧拉序上最后出现的位置，\(c_i\) 表示是否有 \(k\in[1,v]\) 满足 \(\operatorname{lst}_{p_k}=i\)（\(1/0\)），问题即求
\[\sum_{i=1}^{2n} c_i\operatorname{dis}(\operatorname{rmq}(\operatorname{lst}_x,i))\quad(\text{若}\operatorname{lst}_x>i\text{则将它们交换一下然后代入区间}) \]求 \(\large \sum_{i=l}^r c(i)w(\operatorname{rmq}(x,i))\)，比较典，可以观察这个题和这篇题解。先把询问拆成 \(1\le i\le \operatorname{lst}_x\)（向左）和 \(\operatorname{lst}_x\le i\le 2n\)（向右）两部分，完全对称，讨论向右的情况。
考虑线段树，每个结点 \([l,r]\) 维护前缀信息，即
\[S=\sum_{i=l}^r c_i\operatorname{dis}(\operatorname{rmq}(l,i)) \]询问就是把 \([\operatorname{lst}_x,2n]\) 拆成 \(\log\) 个区间然后从左到右依次合并。考虑如何合并 \([l_0,l-1]\) 与 \([l,r]\)。柱子高度表示 \(\operatorname{dep}(\operatorname{rmq}(l,i))\)。
注意到，\(l_0\) 到 \(l-1\) 每一位的贡献不变，记 \(p\) 为最靠左的位置满足 \(\operatorname{dep}(\operatorname{rmq}(l,p))\le \operatorname{dep}(\operatorname{rmq}(l_0,l-1))\)，那么 \(p\) 到 \(r\) 每一位的贡献也不变。唯一的变化是，\([l,p-1]\) 中每一位的 \(\operatorname{rmq}\) 都被推平成了 \(\operatorname{rmq}(l_0,l-1)\)。
于是可以用线段树二分求 \(p\)，同时求出 \(p\) 右侧不变的答案与左侧的 \(\sum_{i=l}^{p-1}\) \(c_i\)。具体地，每个结点额外维护 \(C\) 表示区间内 \(c_i\) 之和，若左儿子的 \(\operatorname{dep}(\operatorname{rmq})\le \operatorname{dep}(\operatorname{rmq}(l_0,l-1))\) 则 \(S\) 加上 \((\text{当前结点}-\text{左儿子})\) 并向左递归，反之 \(C\) 加上左儿子并向右递归。最后用得到的 \(C\) 算 \([l,p-1]\) 的贡献即可。
一次合并 \(\Theta(\log n)\)，查询就是 \(\Theta(\log^2 n)\)。
对于插入/删除 \(p_i\)，它等价于单点 \(c_i\) 加减 \(1\)。那么包含这个点的所有区间，其 \(S\) 都要加上或减去左端点到这个点的 \(\operatorname{dis}(\operatorname{rmq})\)。这个随便做。总复杂度 \(\Theta(n\log n+m\log^2 n)\)，空间复杂度 \(\Theta(n\log n)\)。
然而，这个做法常数极大。查询的 \(\Theta(\log^2 n)\) 一定会跑满。一开始我修改操作求 \(\operatorname{rmq}\) 还是在线段树上暴力求的，导致修改也变成了 \(\Theta(\log^2 n)\)，直接 T 飞。把 \(\operatorname{rmq}\) 换成 ST 表，多出来的 \(14\text{MB}\) 左右让空间当场爆炸。优化求 \(\operatorname{rmq}\) 的过程，在递归修改过程中直接用左右儿子更新，扔掉 ST 表，空间仍然卡不过去。
于是考虑引进 dfs 序求 LCA。实现上，把所有欧拉序全部换成 \(\operatorname{dfn}\)，\(\operatorname{dis}\) 换成 \(\operatorname{fa}(\operatorname{dis})\)，开两棵线段树，修改的时候一棵在 \(\operatorname{dfn}(p_i)+1\) 处改，另一棵在 \(\operatorname{dfn}(p_i)\) 处改，查向左就在第一棵用 \(\operatorname{dfn}(x)\)，向右就是第二棵用 \(\operatorname{dfn}(x)+1\)，最后加上 \(x=p_i\) 的特判。这个还是两倍常数，但是线段树上少了 \(2n\) 个根节点，存 \(\operatorname{dfn}\) 的数组少了 \(n\)，这不到 \(3\text{MB}\) 的空间直接让我卡过去了。主席树数组大小 \(57n\) 会不够，\(60n\) 会 MLE，\(59n\) 可以过。非常极限。
如果有吊打此题解的卡空间技巧，可以娇娇我。
标签：rmq,log,题解,lst,CF757G,Theta,operatorname,dis From： https://www.cnblogs.com/vanspace/p/CF757G.html