1483: [HNOI2009]梦幻布丁

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 4022  Solved: 1640

[][][]

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。

n,m<=1000000

Output

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

Sample Input

4 3

1 2 2 1

2

1 2 1

2

Sample Output

3

1

 

/*vector 记录每个颜色出现的位置修改时启发式合并，更细答案即可。 */#include
      
       #define N 1000007#define inf 0x3f3f3f3f#define ll long longusing namespace std;vector
       
        v[N];vector
        
         ::iterator it;int n,m;int fa[N],a[N];int main(){    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++;        fa[a[i]]=a[i];        v[a[i]].push_back(i);    }    while(m--)    {        int t;        scanf("%d",&t);        if(t==2) printf("%d\n",ans);        else        {            int x,z;            scanf("%d%d",&x,&z);            if(x==z)continue;            if(v[fa[x]].size()>v[fa[z]].size()) swap(fa[x],fa[z]);            int col1=fa[x],col2=fa[z];            for(int i=0;i