首页 > 代码库 > [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]梦幻补丁（有序表启发式合并）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。