题解：P9295 [POI 2020] Gang Biciaków / 布茨帮

· · 题解

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

根号分治

受到 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