2020-2021:teams:alchemist:weekly_digest_9
这是本文档旧的修订版！
目录
Summer Tranning Week 4
比赛简记
Max.D.
专题
比赛
题目
Hardict
专题
比赛
题目
MountVoom
专题
无
比赛
求求来点cf div1
题目
无
个人总结
陈铭煊 Max.D.
龙鹏宇 Hardict
肖思炀 MountVoom
感觉有些浮躁，希望能静下心来，做题的时候更加集中一些。
本周推荐
陈铭煊 Max.D.
来源：
标签：
题意：
题解：
评论：
龙鹏宇 Hardict
来源：
标签：
题意：
题解：
评论：
肖思炀 MountVoom
来源：
标签：
线段树分治，并查集
题意：
球迷j愿意观看球员i的比赛需要满足：j是i的粉丝或者j和j'都是i'的粉丝且j'是i的粉丝。
选择最少的球员进全明星赛，使得所有球迷都愿意观看。且有q次粉丝关系的修改，x是y的粉丝变为不是，x不是y的粉丝变为是，每次修改都会询问。
题解：
把球员和粉丝相连，答案即为(n个球员的连通分量个数)- (孤立球员个数)，如果有球迷的度为0，则答案为-1。
把每个关系存在的时间划分成线段树上的log个区间，线段树每个节点维护了在这段时间存活的所有边，最后遍历一次线段树即可，因为回溯时需要删边，所以需要用启发式合并的并查集。
最终复杂度为$O(n \log^2 n)$
评论：
比赛做得太慢了以至于没有时间写这道题…
2020-2021/teams/alchemist/weekly_digest_9.1596785743.txt.gz · 最后更改: 2020/08/07 15:35 由 mountvoom
