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颜色不同的个数

 var

     head,sum,f:array[..]of longint;

     next,c:array[..]of longint;

     n,m,ans:longint;

 procedure swap(var x,y:longint);

 var

     t:longint;

 begin

     t:=x;

     x:=y;

     y:=t;

 end;

 procedure init;

 var

     i:longint;

 begin

     read(n,m);

     for i:= to  do

       f[i]:=i;

     for i:= to n do

       begin

         read(c[i]);

         inc(sum[c[i]]);

         next[i]:=head[c[i]];

         head[c[i]]:=i;

         if c[i]<>c[i-] then inc(ans);

       end;

 end;

 procedure work;

 var

     i,q,k1,k2,j,k:longint;

 begin

     for i:= to m do

       begin

         read(q);

         if q= then writeln(ans)

         else

           begin

             read(k1,k2);

             if f[k1]=f[k2] then continue;

             if sum[f[k1]]>sum[f[k2]] then swap(f[k1],f[k2]);

             k1:=f[k1];

             k2:=f[k2];

             if sum[k1]= then continue;

             inc(sum[k2],sum[k1]);

             sum[k1]:=;

             j:=head[k1];

             while j<> do

               begin

                 if c[j]<>c[j-] then dec(ans);

                 if (j<n)and(c[j]<>c[j+]) then dec(ans);

                 j:=next[j];

               end;

             j:=head[k1];

             while j<> do

               begin

                 c[j]:=k2;

                 j:=next[j];

               end;

             j:=head[k1];

             while j<> do

               begin

                 if c[j]<>c[j-] then inc(ans);

                 if (j<n)and(c[j]<>c[j+]) then inc(ans);

                 if next[j]= then k:=j;

                 j:=next[j];

               end;

             swap(head[k1],head[k2]);

             next[k]:=head[k1];

             head[k1]:=;

           end;

       end;

 end;

 begin

     init;

     work;

 end.

巴特西

1483:[HNOI]2009 梦幻布丁 - BZOJ

最新文章

热门文章