【算法】分块 rmq

今天无意中碰到这么一道题: 由乃救爷爷 作为一个 WOT 玩家感觉题面十分亲切 值得一提的是我还真和 lxl 语音联机打过 WOT 题目就是裸的 RMQ 问题 然而数据非常大,普通的 $O(n \log _ 2 n)-O(1)$rmq 肯定是无法通过得了的 笛卡尔树欧拉序 $\pm$rmq 的 $O 阅读更多…

【题解】Lomsat gelral 树上启发式合并 CF – 600E

题目链接 树上启发式合并(dsu on tree)模板题 就是先轻重链剖分,dfs 算答案的时候,先去计算轻儿子的答案,为了防止儿子之间互相影响,每计算完一个儿子就要清空统计信息 然后 dfs 算重儿子答案,此时不清空统计信息,然后再去把所有轻儿子的统计信息算进来就能得到当前点的答案了 这样子每个点 阅读更多…