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

输出格式

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

样例输入

4 3
1 2 2 1
2
1 2 1
2

样例输出

3
1

提示

没有写明提示

题目来源

没有写明来源

补：数据范围：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])。这是很显然的。

代码：

#include <cstdio>
#include <cctype>
#include <list>
#include <algorithm>
using namespace std;
template<typename tp>void read(tp & dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,m,arr[100005],root[1000005],ans;
list<int> l[1000005];
void merge(int a,int b)
{
    for(list<int>::iterator i=l[a].begin();i!=l[a].end();i++)
    {
        l[b].push_back(*i);
        if(arr[*i-1]==b)ans--;
        if(arr[*i+1]==b)ans--;
    }
    for(list<int>::iterator i=l[a].begin();i!=l[a].end();i++)arr[*i]=b;
    l[a].clear();
}
int main()
{
    read(n),read(m);
    for(int i=1;i<=n;i++)
    {
        read(arr[i]);
        if(arr[i]!=arr[i-1])ans++;
        root[arr[i]]=arr[i],l[arr[i]].push_back(i);
    }
    for(int i=1,a,b;i<=m;i++)
    {
        read(a);
        if(a==2)printf("%d\n",ans);
        else
        {
            read(a),read(b);
            if(a==b)continue;
            if(l[root[a]].size()>l[root[b]].size())swap(root[a],root[b]);
            a=root[a],b=root[b];
            merge(a,b);
        }
    }
}