自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:53:47，当前版本为作者最后更新于2024-01-01 00:44:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

nrd。

去年五月的模拟赛题，标算给了个带根号的东西，1kri 分享了一个 pog 做法。

思路

一个很自然的想法是扫描线，每个询问看成一个点，扫到 $l$ 的时候塞进 ds，扫到 $r$ 的时候看看它跑到哪里了。

拿个并查集时刻把重合的点缩起来。

走一步的时候，这个点到根的路径上的点全部往下走，其他点全部往上走。

跨链的时候暴力做。向下跨链，每次操作最多出现 $\log$ 次，就是每条重链一次，总 $n\log$ 次。向上跨链，考虑会塞进去 $n$ 个点，每个点最多向上跨 $\log$ 次，算上向下跨导致的来回走，总的还是 $n\log$ 次。

实现

1kri 当时好像讲了实现但是我忘了，搓了半年才搓出来（？

考虑到重链有 $n$ 个，把所有重链都摸一遍显然是不行的。

我们的 ds 还需要支持快速找到哪些点要跨链了。

枚举了很久做法之后发现大概只能树套树，对每个重链开一个小树，对所有重链开一个大线段树维护深度的最小值，减到 $-1$ 了说明有点跨链了，二分查找到哪个重链，然后暴力修改。因为有平移操作，小树用平衡树可能会比较合适。

一、把询问 $l=i$ 的点挂上去。

二、$i$ 到根的链上的点向下跳一步并处理向下跨链及其产生的合并。

三、所有点向上跳一步。

四、$i$ 到根的链上的点向下跳一步并处理合并。

五、处理向上跨链。

六、记录 $r=i$ 的询问的答案。

先向上后向下会有点连跳两步，见样例第三组询问。

code

大战 nrd。

有个注意的地方是线段树的叶子的懒惰标记要推到平衡树的根上。

代码太长了放在这里。