1. 题目

传送门= ̄ω ̄=

[HNOI2009]梦幻布丁

时间限制:10s 空间限制:64MB

题目描述

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<=n,m<=100,000; 0<Ai,x,y<1,000,000

2. 做法

前面看到神犇pyh在做这道题,远远望去觉得好水啊——~~用分块或者线段树解决不就行了吗?~~
然而……其实是我看错题了。题目是说把某种颜色的布丁改为另一种颜色,而不是把一个区间的布丁改为另一种颜色……

然而其实这样子更水!= ̄ω ̄=
用启发式合并就可以了!

具体怎么搞呢?

首先,我们搞1,000,000个链表(如果你想用别的容器也随你),再搞个数组color[1000000],其中color[i]表示颜色i所对应的链表下表是color[i]。

然后我们再输入的时候与处理好这些链表和color数组,同时遍历一遍,算出最开始的答案ans。

那链表存什么呢?链表存这个链表对应的颜色的那些节点的下标(在输入的数组中的位置)。

而如果我们要让颜色x变成颜色y,就把颜色x对应的链表复制到颜色y对应的链表后面。对于复制过去的每个元素(每个节点下标)(这些节点的颜色都是x)i,我们判断数组中下表为i-1和i+1的节点颜色是否为y,如果为y那么ans--(因为之前i的颜色一定为x,所以它的颜色一定不为y,所以如果i-1或者i+1为y,那么一定是原来不在一段颜色中的两端合并成了一段)。

有了这个我们就得到了暴力解法,复杂度为:O(mn);

这时候我们可以用启发式合并。
思路很简单:合并两个链表的时候,把长度小的合并到长度大的链表里面去。
乍一看复杂度不会减小多少,但是其实这样复杂度就降到了O(mlogn)。
~~至于为什么我不会证。~~

怎么搞呢?就是在把链表a合并到链表b的时候,如果list[a].size()>list[b].size就swap(color[a],color[b])。这是很显然的。

代码: