2021-2022:teams:aaub:2021.8.02_牛客6
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2021-2022:teams:aaub:2021.8.02_牛客6 [2021/08/03 17:03] prime21 |
2021-2022:teams:aaub:2021.8.02_牛客6 [2021/08/03 17:27] (当前版本) hugegun [E: Growing Tree] |
||
|---|---|---|---|
| 行 55: | 行 55: | ||
| 题意：强制在线，动态树上加点，询问子树内的某一个颜色的个数。 | 题意：强制在线，动态树上加点，询问子树内的某一个颜色的个数。 | ||
| - | $n log^2 n$ 做法，开颜色棵splay，splay的顺序为当前树的dfs序，那么子树问题变成splay上一段区间的查询问题，而子树查询还需要知道子树对应的区间的结尾和开头各是哪里，注意到$u$子树内一点$v$满足$lca(u,v) = u$，用这个性质可以寻找dfs序上最后一个满足该性质的点，故在splay上二分查询满足lca性质的最后一个点即可解决问题。 | + | $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.1627981405.txt.gz · 最后更改: 2021/08/03 17:03 由 prime21
