首页 > 其他 > 详细

DTOJ 5214 第一题

时间:2020-11-28 09:34:51      阅读:30      评论:0      收藏:0      [点我收藏+]

题意

给出一个树上点集,树上的每个点可以锁定与解锁。

每次更新对所有未锁定的点有效,把所有相连的点加入点集。

动态询问每个点是否在点集内。

范围:\(n,q\leq5\times 10^5\)

分析

暴力做法对于每次更新遍历所有点,效率\(O(n^2)\)。该做法同样适用于图,引导我们利用树的特殊性质优化算法。

点集的扩散具有方向性,每次更新的点逐渐向外推移,相应地,中间部分应避免重复更新。对于有根树而言,其深浅相当于人为定义的方向性。

在两个方向上分别考虑,发现向上走更新单点,可以打标记处理;向下走更新多点,应当避免无用操作。

  • 上传时,为保证单点复杂度\(O(1)\),不能遍历所有儿子。维护\(cnt[u]\)数组为\(u\)的儿子中被感染且未锁定点的数目,则 $u未被锁定 &&cnt[u]>0 $ 时,u会被其子节点更新。

  • 标记下传操作的主要瓶颈在于“锁定点”及其子树不会被更新,但在解锁后又要单独考虑。因此,可以以每个点的所有儿子作为初始的更新集合,在下传时清空集合,在儿子被解封时再将其放入集合中。

具体实现时需要数组\(\mathtt{cnt[1\dots n]}\),可能会被向上更新的所有点\(\mathtt{updf}\),可能会被向上更新的所有点\(\mathtt{upds}\),以及\(n\)个集合\(\mathtt{down[1\dots n]}\)即上述“更新集合”。此处“集合”可重且无序,用\(\mathtt{vector}\)实现。

复杂度

  • 每个点仅可能被向上更新一次。

  • 每次下传遍历所有边,共\(n-1\)条;解封再次放入集合最多\(q\)

  • \(\mathtt{updf}\)\(\mathtt{upds}\)最多只会被加入元素\(q\)次。

综上所述,总复杂度为\(O(n+q)\)

DTOJ 5214 第一题

原文:https://www.cnblogs.com/ehznehc/p/14050925.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!