限制

        时间限制: 1 Sec 内存限制: 128 MB

题目描述

        N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色。例如颜色分别为1,2,2,1的四个布丁一共有3段颜色。

输入

第一行是两个整数，分别表示布丁个数n和操作次数m。
第二行有n个整数，第i个整数表示第i个布丁的颜色a[i]。
接下来m行，每行描述一次操作。每行首先有一个整数op表示操作类型：

• 若op=1，则后有两个整数 x, y，表示将颜色x的布丁全部变成颜色y。
• 若op=2，则表示一次询问。

输出

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

样例输入

4 3
1 2 2 1
2
1 2 1
2

样例输出

3
1

样例解释

        初始时布丁颜色依次为1,2,2,1，三段颜色分别为[1,1],[2,3],[4,4]。一次操作后，布丁的颜色变为1,1,1,1，只有[1,4] 一段颜色。

数据范围

40%数据n * m <= 3e8
60%数据n * m <= 5e8
1 <= n,m <= 100000; 0 < Ai,x,y < 1000000

提示

不保证颜色的编号不大于n，也不保证x!=y，m不是颜色的编号上限。

分析

        可以用链表来存不同颜色的链表（c数组），用数组xyg来存另一个同颜色的链表，c数组来记录链表的头。

代码

#include<stdio.h>
int n,m,i,j,op,x,y,s,a[100005],xyg[100005],c[1000005];
int main(){scanf("%d%d",&n,&m);for(i=1;i<=n;++i){scanf("%d",&a[i]);xyg[i]=c[a[i]],c[a[i]]=i;if(a[i]!=a[i-1]) ++s;}while(m--){scanf("%d",&op);if(op==1){scanf("%d%d",&x,&y);if(x==y) continue;for(i=c[x];i!=0;i=xyg[i]){if(a[i-1]==y) --s;if(a[i+1]==y) --s;}for(i=c[x];i!=0;i=xyg[i]) a[i]=y,j=i;xyg[j]=c[y],c[y]=c[x],c[x]=0;}else printf("%d\n",s);}return 0;
}