首页 > 其他 > 详细

CF891C Envy(离线/在线+可撤销并查集/并查集/LCT)

时间:2019-09-27 21:45:19      阅读:109      评论:0      收藏:0      [点我收藏+]

前置知识

最小生成树及证明

做法

每个不同权值没影响,仅需判断该次询问每种权值是否在"小于该权值的所有边加完"之后,可以全部加进来

  • 离线:询问的所有边全堆到一起,按权值排序,然后同种权值的同种查询完再撤销

  • 在线:预处理每条边在小于等于该权值的边加完之后所处联通块,然后查询时单独判断每种权值即可

CF891C Envy(离线/在线+可撤销并查集/并查集/LCT)

原文:https://www.cnblogs.com/y2823774827y/p/11600426.html

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