bzoj3123

转移自老blog

bzoj3123

链接

题意

        1.求森林任意路径第k大，2.森林合并，森林点个数1e5

题解

        在主席树上加上启发式合并即可，合并的时候更新lca的倍增数组，启发式生成新的主席树，可以证明合并的均摊时间复杂度为lg级别
ACM > 老Blog迁移 > reading_problem
bzoj3123
http://fightinggg.github.io/fluid/bzoj3123.html
作者
fightinggg
发布于
2019年8月5日
许可协议