1483:[HNOI]2009 梦幻布丁

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

1 2 1

Sample Output

把每种颜色的布丁做成一个链表，每次把两个链表合并，用启发式合并，时间均摊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.

View Code