2021-2022:teams:aaub:2021.8.02_牛客6

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2021-2022:teams:aaub:2021.8.02_牛客6 [2021/08/03 00:38]
prime21 [D: Gambling Monster]
+++ 2021-2022:teams:aaub:2021.8.02_牛客6 [2021/08/03 17:27] (当前版本)
hugegun [E: Growing Tree]
@@ 行 50: / 行 50: @@
 ----
+==== E: Growing Tree ====
+题意：强制在线，动态树上加点，询问子树内的某一个颜色的个数。
+$n \log^2 n$ 做法，开颜色棵splay，splay的顺序为当前树的dfs序，那么子树问题变成splay上一段区间的查询问题，而子树查询还需要知道子树对应的区间的结尾和开头各是哪里，注意到$u$子树内一点$v$满足$lca(u,v) = u$，用这个性质可以寻找dfs序上最后一个满足该性质的点，故在splay上二分查询满足lca性质的最后一个点即可解决问题。
+分块：设置块大小$BLK$，暴力建树、查询，树大小超过$BLK$就把这部分按dfs序加到序列中，查询时按$u$在树中和序列中两种情况处理。(邻接表用vector太慢了，实际上和log^2差不多)

2021-2022/teams/aaub/2021.8.02_牛客6.1627922325.txt.gz · 最后更改: 2021/08/03 00:38 由 prime21