题解 P4230 【连环病原体】

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)