1483: [HNOI2009]梦幻布丁
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 3481 Solved: 1374
[Submit][Status][Discuss]
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
1 2 2 1
2
1 2 1
2
Sample Output
3
1
1
HINT
Source
启发式合并的题目
启发式合并就是把小的向大的里面合并
这样显然要更快一点（似乎是这样吧）
于是乎就起了一个这么高大上的名字~~~
首先这题最显著的特征就是，你把1变成2和2变成1在处理上可以没有区别
所以我们把小的向大的里面合并，比如1出现了999999次，2出现了1次，题目叫你把1变成2，显然不会听它的！
但是要注意，我们需要定义一个数组(cha)，来记录1和2，否则就分不清楚了，每当出现上述情况时，swap一下即可
具体实现方式可以是链表，每种颜色做一个链表记录位置，然后a变成b就把a接在b后面即可
1 /************************************************************** 2 Problem: 1483 3 User: white_hat_hacker 4 Language: C++ 5 Result: Accepted 6 Time:336 ms 7 Memory:24260 kb 8 ****************************************************************/ 9 10 #include<cstdio> 11 #include<cstdlib> 12 #include<algorithm> 13 #include<cstring> 14 #define MAXN 1000005 15 using namespace std; 16 int a[MAXN]; 17 int ans; 18 int head[MAXN],Next[MAXN]; 19 int n; 20 int cnt[MAXN]; 21 int ed[MAXN]; 22 int cha[MAXN]; 23 int read(){ 24 int x=0;char ch=getchar(); 25 while(ch<'0'||ch>'9'){ch=getchar();} 26 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 27 return x; 28 } 29 void solve(int x,int y){ 30 for(int i=head[x];i;i=Next[i]){ 31 if(a[i-1]==y) ans--; 32 if(a[i+1]==y) ans--; 33 } 34 for(int i=head[x];i;i=Next[i]){ 35 a[i]=y; 36 } 37 cnt[y]+=cnt[x]; 38 Next[ed[y]]=head[x]; 39 ed[y]=ed[x]; 40 head[x]=cnt[x]=ed[x]=0; 41 } 42 int main() 43 { 44 // freopen("pudding6.in","r",stdin); 45 // freopen("pudding.out","w",stdout); 46 n=read(); 47 int T=read(); 48 for(int i=1;i<=n;i++){ 49 a[i]=read(); 50 if(a[i]==a[i-1]){ 51 n--;i--; 52 continue; 53 } 54 cha[a[i]]=a[i]; 55 if(!head[a[i]])ed[a[i]]=i; 56 cnt[a[i]]++; 57 ans++; 58 Next[i]=head[a[i]];head[a[i]]=i; 59 } 60 for(int i=1;i<=T;i++){ 61 int p=read(); 62 if(2==p){ 63 printf("%d ",ans); 64 } 65 else{ 66 int x=read(),y=read(); 67 if(x==y){ 68 continue; 69 } 70 if(cnt[cha[x]]>cnt[cha[y]]){ 71 swap(cha[x],cha[y]); 72 } 73 x=cha[x],y=cha[y]; 74 if(!cnt[x]){ 75 continue; 76 } 77 solve(x,y); 78 } 79 } 80 return 0; 81 } 82
也可以用set省事，高大上一点就叫平衡树+启发式合并
1 /************************************************************** 2 Problem: 1483 3 User: white_hat_hacker 4 Language: C++ 5 Result: Accepted 6 Time:792 ms 7 Memory:34320 kb 8 ****************************************************************/ 9 10 #include<cstdio> 11 #include<cstdlib> 12 #include<algorithm> 13 #include<cstring> 14 #include<set> 15 #define MAXN 1000005 16 using namespace std; 17 int read(){ 18 int x=0;char ch=getchar(); 19 while(ch<'0'||ch>'9'){ch=getchar();} 20 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 21 return x; 22 } 23 set<int> s[MAXN]; 24 int n; 25 int a[MAXN]; 26 int cha[MAXN]; 27 int ans; 28 void solve(int x,int y){ 29 for(set<int>::iterator i=s[x].begin();i!=s[x].end();i++){ 30 int p=(*i); 31 if(y==a[p-1]) ans--; 32 if(y==a[p+1]) ans--; 33 s[y].insert(p); 34 } 35 for(set<int>::iterator i=s[x].begin();i!=s[x].end();i++){ 36 int p=(*i); 37 a[p]=y; 38 } 39 s[x].clear(); 40 } 41 int main() 42 { 43 // freopen("pudding1.in","r",stdin); 44 // freopen("my.out","w",stdout); 45 n=read(); 46 int T=read(); 47 for(int i=1;i<=n;i++){ 48 a[i]=read(); 49 if(a[i]==a[i-1]){ 50 n--;i--; 51 continue; 52 } 53 ans++; 54 cha[a[i]]=a[i]; 55 s[a[i]].insert(i); 56 } 57 for(int i=1;i<=T;i++){ 58 int p=read(); 59 if(2==p){ 60 printf("%d ",ans); 61 } 62 else{ 63 int x=read(),y=read(); 64 if(x==y){ 65 continue; 66 } 67 if(s[cha[x]].size()>s[cha[y]].size()){ 68 swap(cha[x],cha[y]); 69 } 70 x=cha[x],y=cha[y]; 71 if(s[x].size()==0){ 72 continue; 73 } 74 solve(x,y); 75 } 76 } 77 return 0; 78 }