http://www.lydsy.com/JudgeOnline/problem.php?id=1483
题意：
思路：
每次修改的话需要把同一种颜色的都修改了，那如果去遍历的话就复杂度比较高，如果用链表把颜色相同的连接起来的话那么修改起来就十分方便了。
但是当两个链表需要合并的时候，修改长度短的那一个相对来说会比较省时，这就是启发式合并。但是使用启发式合并的话需要注意，如果现在有操作1->2，本来是要将所有的1改成2，如果1的链表长度大于2的链表长度的话，启发式合并就会将2合并至1，此时也就变成了将2变成1，所以我们需要一个数组pos来记录所要找的颜色在链表中实际对应的颜色。
那么当修改颜色时怎么动态维护答案呢，我们只需要扫描一遍链表，如果此时是x->y，如果颜色为x的某个数左边为y，那么ans--，右边为y，那么ans--。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn = 1000000+5;
int n, m;
int a[maxn],sz[maxn],nxt[maxn],frt[maxn],pos[maxn];
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
int ans = 0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]!=a[i-1]) ans++;
sz[a[i]]++;
pos[a[i]]=a[i];
nxt[i]=frt[a[i]],frt[a[i]]=i;
}
while(m--)
{
int op;
scanf("%d",&op);
if(op==1)
{
int x,y,num;
scanf("%d%d",&x,&y);
if(x==y) continue;
if(sz[pos[x]]>sz[pos[y]]) swap(pos[x],pos[y]);
x=pos[x],y=pos[y];
if(!sz[x]) continue;
for(int i=frt[x];i;i=nxt[i])
{
if(a[i+1]==y) ans--;
if(a[i-1]==y) ans--;
num = i;
}
for(int i=frt[x];i;i=nxt[i]) a[i]=y;
sz[y]+=sz[x],sz[x]=0;
nxt[num]=frt[y];
frt[y] = frt[x];
frt[x] = 0;
}
else printf("%d\n",ans);
}
return 0;
}