题解 P4230 【连环病原体】

官方题解有剧情哦~ 剧情版题解见最下面 可读题面： 一张n点m边无向图，每条边有编号 若一个区间内的边能连成一个环(cycle)，则称这个区间为好区间 求每条边分别在多少个好区间内 解法0： 我不会做！输出一堆0试试看 期望得分0分，实际得分5分 这个测试点是用来安慰正解写挂的同学们的 解法1： 我会DFS/并查集！ 枚举每个区间，DFS判断有没有环，再更新区间内的边的答案 时间复杂度$O(n^2)$或$O(n^2 \alpha(n))$，期望得分60分，实际得分60分 解法2： 我会LCT！ 固定区间的左端点，将区间的右端点向右移动，用LCT维护区间内是否有环，如果有环就把左端点向右移动直到没有环为止 用两次前缀和维护一下答案 时间复杂度$O(nlogn)$，期望得分100分，实际得分75~100分 FAQ：为什么我写了LCT却只得了75分/90分 A：因为findroot后要splay才能保证复杂度，不splay的都被我卡到$O(n^2)$啦！ -----------------------------------下面是剧情--------------------------------------- （二）连环病原体 其实，这个问题并不复杂呢。 我们把病原体看做点，影响看做边。 这些边按照编号排序，就形成了一个序列。 一个区间，就是这个序列中的某一段。 那么，对于所有的区间，我们把这些点和边画出来，看看有没有环就可以了，有环的话，说明区间内的每一条边的重要程度都要增加1。 把这个想法告诉山女吧。 "对哦，这样就可以了呢"，山女说道。 "不过先别急着走" "你看，我这里有几万个病毒，它们之间的影响甚至有20 万种，那么区间的数量可能达到20 万的平方！这太多了吧！" 对哦，想一想，区间的左端点有m 种选择，右端点的选择数量也是m 这个级别的，那么区间的数量确实是m 的平方级别的，20 万的平方太可怕了。 哇，她居然懂这些，地底的妖怪果然不可小看呢。 不过，她没有意识到一点哦，我还得解释一下。 "其实，也没有这么多吧？"我说道。 "你看，如果我让左端点为1，右端点和左端点重合，然后右端点不断向右边推进，扩大这个区间。" "每次遇到一条边，都加进这幅图里，直到产生了一个环为止。" 山女:"那又怎样呢？没看出少了哪啊" "不，产生一个环之后，右端点就不需要再往右推进了，因为后面的区间肯定都是有环的。在只增加边的情况下，环是不会消失的！" 山女:"对哦，这样就省了很多功夫，但区间的数量还是平方级别的啊，有可能一直没遇到环，推到最后了呢。" 我:"然后，这里就是重点了。在遇到第一个环时，区间的右端点就不用继续推进了，只要记录下结果，然后左端点+1 就行。" ...... 山女:"然后右端点回到左端点，继续加边，重复刚才的动作？" 我:"右端点不用回到左端点！只要继续推进就可以。因为左端点+1 后，少了一个边啊， 刚才没少边时，右端点之前的那一段边全加进去都没有出现环，少了一条边就更不可能有环了。" ...... 山女:"嗯....妙啊，这样的话，左端点和右端点都只向右推进，而不回头，我要处理的区间数量就不再是m 平方级别，而是m 级别的了，是一个大的进步啊。" ...... 山女:"但是，还有个问题" "什么？" 山女:"怎样统计？这似乎是一个给很多段区间的值都+1 的问题，可以看成给一段区间增加一个每次递减1 的等差数列" 意料之外的事情出现了。 我的脑子突然一片空白，好像确实忽略了这个问题。 "哇，这个我也不会诶",我只好这么说。 山女:"好吧好吧，不会就算了，今天你帮我了一个大忙呢，你们先继续旅行吧，我请桥姬给你们带路"。 ...... 就这样，旅行还要继续下去。 水桥帕露西作为带路人加入了我们的旅行，她会把我们带到旧地狱的街市。 帕露西:"真嫉妒啊，你们说的话我完全听不懂" 我:"我也没想到呢，地底的妖怪的理解力这么强。" 帕露西:"她为了更好地研究疾病，去红魔馆的大图书馆借了各种方面的书，所以会懂那么多的吧。" 我:"可能吧" 帕露西:"对了，这些我听不懂的东西是关于哪个方面的" 我:"计算机程序，算法，数据结构"。 帕露西:"计算机？？？ 我在妖怪之山的河童那里听到过，不是只能记录东西，算算数学，玩玩游戏吗？" 我:"计算机很深奥的啦" 帕露西:"真是嫉妒，我一点都不懂" （接t2）