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

差别

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

到此差别页面的链接

--- 2021-2022:teams:aaub:2021.8.02_牛客6 [2021/08/03 00:08]
prime21 [J: Defend Your Country]
+++ 2021-2022:teams:aaub:2021.8.02_牛客6 [2021/08/03 17:27] (当前版本)
hugegun [E: Growing Tree]
@@ 行 4: / 行 4: @@
 考场构造了两个小时也没玩明白
+zyy: done
 ----
@@ 行 40: / 行 42: @@
 ----
+==== D: Gambling Monster ====
+pmxm: 考场想到直接推期望就好了$x \oplus y > x$会被分成$\log$段，然后发现不会做每个概率都不一样的情况。
+实际上转移方程是卷积的形式，所以用分治处理卷积转移的方式就可以了。
+----
+==== 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.1627920528.txt.gz · 最后更改: 2021/08/03 00:08 由 prime21