当前位置:首页 > 启发式合并 > 正文
BZOJ1483[HNOI2009]梦幻布丁
3738+

题目大意:n个有颜色的补丁,你可以随时将某种颜色的布丁变成另外一种颜色,请问操作过程中分别有多少段颜色?

题目描述

N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.

输入输出格式

输入格式:

第一行给出N,M表示布丁的个数和好友的操作次数. 第二行N个数A1,A2…An表示第i个布丁的颜色从第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变,其后的两个整数X,Y表示将所有颜色为X的变为Y,X可能等于Y. 若第一个数字为2表示要进行询问当前有多少段颜色,这时你应该输出一个整数. 0

输出格式:

针对第二类操作即询问,依次输出当前有多少段颜色.

输入输出样例

输入样例#1:

4 3
1 2 2 1
2
1 2 1
2

输出样例#1:

3
1

说明

1<=n,m<=100,000; 0<Ai,x,y<1,000,000

解题思路

暴力做法:对于每次更改颜色x为y,可以枚举n个布丁,如果布丁颜色是x那么将其颜色改成y;对于询问有多少段颜色,同样枚举n个布丁,如果发现当前布丁与前一个布丁颜色不同,累加颜色段数;时间复杂度是O(nm),结果是超时。

如何优化呢?m次操作,O(m)无法优化;对于更改颜色方面,极端情况是n个布丁都需要更改颜色,但如果我们更改颜色时,选颜色布丁少的那种颜色来变,并开一个数组记录每种颜色对应的编号,这样修改次数就大大减少了!当然,复杂度没有变化,因为还需要遍历n个布丁。如果用链表就只需要遍历该颜色的布丁而已,复杂度就可以降低到log级别了,这就是链表的启发式合并。

先说合并,如5个布丁,颜色分别是1 2 2 2 2,操作是把颜色2改成颜色1,如果直接操作,需要改4次颜色,最终变成1 1 1 1 1,但如果把1改成2才需要改1次颜色,最终变成2 2 2 2 2。如果后面又要把颜色1改成颜色2,前者可以继续改,后者就找不到1了,但实际上颜色全是1,怎么办呢?用一个数组记录每一种颜色对应的编号!颜色编号分别是1 2 2 2 2,操作是把颜色2改成颜色1,最终变成2 2 2 2 2时,同时需要更新颜色1的编号是2,颜色2的编号是1。若下次要把颜色1改成颜色2,那么颜色1的编号改成颜色2的编号还是可以继续操作的(将颜色编号数组中的2变成1)。

每次把颜色少的合并到颜色多的,多次合并后,每次合并均摊复杂度是log级别的,为什么呢?

因为每一种颜色,只要变为另外一种颜色,那么他所在集合就至少扩大一倍(另外一种颜色不比他少);也就是说,对于每一个元素,更改颜色次数不会超过log(n),如果超过了,那么总数必超过n!

对于查询颜色段数,可以在合并过程中顺便处理好:如果改布丁修改颜色后,根旁边的布丁颜色一样,那么颜色段数减少1。注意,旁边包括左边和右边,需要分开计算。处理好段数后,再进行修改,修改完后,合并两个链表,可以用这种形式:h[x] … w[x] → h[y],然后h[y] = h[x],颜色个数只需要累加和清零就行。

整体时间复杂度:O(m*log(n))

程序实现

线段树合并,自动“启发式”,遇到一个子树为空整棵树O(1)合并,效率更高。因为一共n个位置,每个位置至多被合并1次,每次一条路log,总的复杂度O(nlogn)。

About

坚决不Copy代码!

本文标签:,,,,,,,

BZOJ1483[HNOI2009]梦幻布丁:目前有1 条留言

发表评论

您必须 [ 登录 ] 才能发表留言!