P9999 [Ynoi2000] tmostnrd 题解

· · 题解

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。

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

代码太长了放在这里。