首页 > 代码库 > bzoj 1483: [HNOI2009]梦幻布丁 启发式合并vector
bzoj 1483: [HNOI2009]梦幻布丁 启发式合并vector
1483: [HNOI2009]梦幻布丁
Time Limit: 10 Sec Memory Limit: 64 MB[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
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
原理: 一个元素从一个集合被加入另一个集合时, 所在集合的规模至少扩大一倍. 如果没有分离操作且元素数目有限, 合并的次数是O(lg n)的.
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<algorithm>#include<stack>#include<cstring>#include<vector>#include<list>#include<set>#include<map>using namespace std;#define ll long long#define pi (4*atan(1.0))#define eps 1e-14#define bug(x) cout<<"bug"<<x<<endl;const int N=1e6+10,M=1e6+10,inf=2147483647;const ll INF=1e18+10,mod=1e9+7;/// 数组大小vector<int>v[N];vector<int>::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 xx=fa[x],zz=fa[z]; for(int i=0;i<v[xx].size();i++) { v[zz].push_back(v[xx][i]); if(a[v[xx][i]-1]==zz)ans--; if(a[v[xx][i]+1]==zz)ans--; } for(int i=0;i!=v[xx].size();i++) a[v[xx][i]]=zz; v[xx].clear(); } } return 0;}
bzoj 1483: [HNOI2009]梦幻布丁 启发式合并vector
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。