自动搬运

查看原文

来自洛谷，原作者为

	dream10 **

搬运于2025-08-24 22:47:05，当前版本为作者最后更新于2025-06-14 23:27:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

简单做个贡献，笔者写的时候洛谷上只有一篇题解。直接进入主题。

根号分治

受到 $m$ 较小和一条链性质的启发，发现一个颜色次数多可以直接开数据结构统计，次数少可以找到关键点，于是根号分治。

具体地，对于一个出现次数比较少的颜色，如果一个点被在另外一个点的子树里就去掉它，然后这些就是关键点，用数据结构维护；出现次数较多的点，就单独开数据结构维护。询问就遍历这些数据结构。

至于优化，就是可以询问离线，找到有潜力变大的颜色，就不用动态分配多少颜色了。

还有就是询问和修改的次数不等，可以值域分块。

还是过不去，但是有意义。$O(n\sqrt{n}\log n)$

https://www.luogu.com.cn/record/220532398

带修莫队

阅读理解。

两个信息，dfs 序列右端点，和时间，莫队即可，是一个根号。$O(n\sqrt{n})$

https://github.com/mrugacz95/oi28/blob/master/gan/gan.cpp

根号重构

重构完进行dfs，遇到询问把可以造成影响的造成影响。$O(n\sqrt{n})$

https://www.luogu.com/article/xt3aitra