传送门:

BZOJ

洛谷


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


解题思路:

这道题可以线段树合并,也可以splay合并…当然也可以set合并…

我们考虑题目要我们求的其实是1+\sum\limits_{i=2}^{n}a[i]!=a[i-1],那么我们对于每个颜色维护一个set,然后合并就好了。

Code:

/*Program from Luvwgyx*/
#include<set>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+10;
int n,m,ans,a[maxn];set<int >s[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
int main(){
    n=read();m=read(),ans=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(a[i]!=a[i-1])ans++;
        s[a[i]].insert(i);
    }
    while(m--){
        int opt=read();
        if(opt==2)write(ans);
        else {
            int x=read(),y=read();if(x==y)continue;
            if(s[x].size()>s[y].size())swap(s[x],s[y]);
            for(set<int > :: iterator it=s[x].begin();it!=s[x].end();it++)ans-=s[y].count(*it-1)+s[y].count(*it+1);
            for(set<int > :: iterator it=s[x].begin();it!=s[x].end();it++)s[y].insert(*it);s[x].clear();
        }
    }
    return 0;
}