题目描述
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<=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("%dn",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 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
