N个布丁摆成一行,进行M次操作.每次将某个颜色的布丁全部变成另一种颜色的,然后再询问当前一共有多少段颜色.例如颜色分别为1,2,2,1的四个布丁一共有3段颜色.
输入格式:
第一行给出N,M表示布丁的个数和好友的操作次数. 第二行N个数A1,A2...An表示第i个布丁的颜色从第三行起有M行,对于每个操作,若第一个数字是1表示要对颜色进行改变,其后的两个整数X,Y表示将所有颜色为X的变为Y,X可能等于Y. 若第一个数字为2表示要进行询问当前有多少段颜色,这时你应该输出一个整数. 0
输出格式:
针对第二类操作即询问,依次输出当前有多少段颜色.
输入样例#1:
4 3
1 2 2 1
2
1 2 1
2
输出样例#1:
3
1
1<=n,m<=100,000; 0<Ai,x,y<1,000,000
用N个平衡树维护这N个颜色出现的位置
就本题而言,完全可以用一个set水过
每次合并的时候暴力合并就可以
注意当读入的颜色相同的时候直接跳出
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<ctime>
5 #include<cstdlib>
6 #include<algorithm>
7 #include<set>
8 using namespace std;
9 #define ls T[now].ch[0]
10 #define rs T[now].ch[1]
11 const int MAXN=1e6+10;
12 inline char nc()
13 {
14 static char buf[MAXN],*p1=buf,*p2=buf;
15 return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
16 }
17 inline int read()
18 {
19 char c=nc();int x=0,f=1;
20 while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
21 while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}
22 return x*f;
23 }
24 set<int>s[MAXN];
25 int a[MAXN],f[MAXN],ans;
26 void unionn(int x,int y)
27 {
28 for(set<int>::iterator i=s[x].begin();i!=s[x].end();i++)
29 {
30 if(a[*i-1]==y) ans--;
31 if(a[*i+1]==y) ans--;
32 s[y].insert(*i);
33 }
34 for(set<int>::iterator i=s[x].begin();i!=s[x].end();i++)
35 a[*i]=y;
36 s[x].clear();
37 }
38 int main()
39 {
40 #ifdef WIN32
41 freopen("a.in","r",stdin);
42 #else
43 #endif
44 int n=read(),m=read();
45 for(int i=1;i<=n;i++)
46 {
47 a[i]=read();
48 if(a[i]!=a[i-1]) ans++;
49 f[a[i]]=a[i];
50 s[a[i]].insert(i);
51 }
52 while(m--)
53 {
54 int opt=read();
55 if(opt==2) { printf("%d\n",ans);continue;}
56 int a=read(),b=read();
57 if(a==b) continue;
58 if(s[f[a]].size()>s[f[b]].size()) swap(f[a],f[b]);
59 unionn(f[a],f[b]);
60 }
61 return 0;
62 }