Description
N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.
Input
第一行给出N,M表示布丁的个数和好友的操作次数. 第二行N个数A1,A2...An表示第i个布丁的颜色从第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变，其后的两个整数X,Y表示将所有颜色为X的变为Y，X可能等于Y. 若第一个数字为2表示要进行询问当前有多少段颜色，这时你应该输出一个整数. 0
Output
针对第二类操作即询问，依次输出当前有多少段颜色.
Sample Input
4 3
1 2 2 1
2
1 2 1
2
Sample Output
3
1
把每种颜色的布丁做成一个链表，每次把两个链表合并，用启发式合并，时间均摊O(mlogn)
我们算答案的时候是相邻的不同颜色就加1，所以我们先减去与X颜色有关的，即把ans减去X相邻的与X不同的有多少个
把X变成Y以后再加上变成Y的相邻的与Y颜色不同的个数
1 var 2 head,sum,f:array[0..1000010]of longint; 3 next,c:array[0..100010]of longint; 4 n,m,ans:longint; 5 6 procedure swap(var x,y:longint); 7 var 8 t:longint; 9 begin 10 t:=x; 11 x:=y; 12 y:=t; 13 end; 14 15 procedure init; 16 var 17 i:longint; 18 begin 19 read(n,m); 20 for i:=1 to 1000000 do 21 f[i]:=i; 22 for i:=1 to n do 23 begin 24 read(c[i]); 25 inc(sum[c[i]]); 26 next[i]:=head[c[i]]; 27 head[c[i]]:=i; 28 if c[i]<>c[i-1] then inc(ans); 29 end; 30 end; 31 32 procedure work; 33 var 34 i,q,k1,k2,j,k:longint; 35 begin 36 for i:=1 to m do 37 begin 38 read(q); 39 if q=2 then writeln(ans) 40 else 41 begin 42 read(k1,k2); 43 if f[k1]=f[k2] then continue; 44 if sum[f[k1]]>sum[f[k2]] then swap(f[k1],f[k2]); 45 k1:=f[k1]; 46 k2:=f[k2]; 47 if sum[k1]=0 then continue; 48 inc(sum[k2],sum[k1]); 49 sum[k1]:=0; 50 j:=head[k1]; 51 while j<>0 do 52 begin 53 if c[j]<>c[j-1] then dec(ans); 54 if (j<n)and(c[j]<>c[j+1]) then dec(ans); 55 j:=next[j]; 56 end; 57 j:=head[k1]; 58 while j<>0 do 59 begin 60 c[j]:=k2; 61 j:=next[j]; 62 end; 63 j:=head[k1]; 64 while j<>0 do 65 begin 66 if c[j]<>c[j-1] then inc(ans); 67 if (j<n)and(c[j]<>c[j+1]) then inc(ans); 68 if next[j]=0 then k:=j; 69 j:=next[j]; 70 end; 71 swap(head[k1],head[k2]); 72 next[k]:=head[k1]; 73 head[k1]:=0; 74 end; 75 end; 76 end; 77 78 begin 79 init; 80 work; 81 end.
1483:[HNOI]2009 梦幻布丁 - BZOJ,布布扣,bubuko.com
原文：http://www.cnblogs.com/Randolph87/p/3583817.html
