首页 > 代码库 > [BZOJ 1483][HNOI 2009]梦幻补丁(有序表启发式合并)

[BZOJ 1483][HNOI 2009]梦幻补丁(有序表启发式合并)

题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1483

分析:

先将不同的颜色的出现位置从小到大用几条链表串起来,然后统计一下答案

对于每次修改,修改一下答案即可,修改之后需要将两个颜色的链表合并就行了,但感觉似乎会TLE?

以下摘录与Hzwer的blog:

1:将两个队列合并,有若干队列,总长度为n,直接合并,最坏O(N),
 
2:启发式合并呢?
 
每次我们把短的合并到长的上面去,O(短的长度)
 
咋看之下没有多大区别,
 
下面让我们看看均摊的情况:
 
1:每次O(N)
2:每次合并后,队列长度一定大于等于原来短的长度的两倍。
 
这样相当于每次合并都会让短的长度扩大一倍以上,
 
最多扩大logN次,所以总复杂度O(NlogN),每次O(logN)。
 
所以只要启发式合并就不会TLE了

[BZOJ 1483][HNOI 2009]梦幻补丁(有序表启发式合并)