自动搬运

查看原文

来自洛谷，原作者为

	oscar **

搬运于2025-08-24 21:57:54，当前版本为作者最后更新于2018-02-15 12:39:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

官方题解有剧情哦~

剧情版题解见最下面

可读题面：

一张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）