首页 > 代码库 > 启发式合并复习
启发式合并复习
T1 永无乡
初做：2017.3.8
http://www.cnblogs.com/TheRoadToTheGold/p/6520714.html
现在：2017.3.30
大约2个半小时
许多点，点有点权，2个操作：连边、询问与某个点相连的点权的k值
#include<cstdio>#include<algorithm>#define N 100001using namespace std;int n,m,tot,cnt,fa[N];int sum[N*20],lc[N*20],rc[N*20],root[N];int key[N],hashh[N];int find(int i) { return fa[i]==i ? i: fa[i]=find(fa[i]); }void insert(int & now,int l,int r,int w){ if(!now) now=++cnt; sum[now]++; if(l==r) return; int mid=l+r>>1; if(w<=mid) insert(lc[now],l,mid,w); else insert(rc[now],mid+1,r,w);}int query(int now,int l,int r,int w){ if(l==r) return hashh[l]; int mid=l+r>>1; if(w<=sum[lc[now]]) return query(lc[now],l,mid,w); else return query(rc[now],mid+1,r,w-sum[lc[now]]);}int unionn(int x,int y){ if(!x) return y; if(!y) return x; lc[x]=unionn(lc[x],lc[y]); rc[x]=unionn(rc[x],rc[y]); sum[x]=sum[lc[x]]+sum[rc[x]]; return x;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&key[i]); fa[i]=i; hashh[key[i]]=i; } int x,y,r1,r2; while(m--) { scanf("%d%d",&x,&y); r1=find(x);r2=find(y); if(r1!=r2) fa[r2]=r1; } for(int i=1;i<=n;i++) insert(root[find(i)],1,n,key[i]); scanf("%d",&m); char c[1]; while(m--) { scanf("%s%d%d",c,&x,&y); if(c[0]==‘B‘) { r1=find(x);r2=find(y); if(r1!=r2) { fa[r2]=r1; unionn(root[r1],root[r2]); } } else { x=find(x); if(y>sum[root[x]]) printf("-1\n"); else printf("%d\n",query(root[x],1,n,y)); } }}
首先，自恃做过一遍不读完题，上来写了一个离散化点权
题目中写着点权1——n，所以不用离散化
顺手写的错误：
if(r1!=r2){ fa[r2]=r1; unionn(r1,r2);}
应该是
unionn(root[r1],root[r2]);
并查集写太熟了，以后注意思考
本质错误：合并
错误合并1：
void unionn(int & x,int y){ if(!y) return; if(!x) x=++cnt; sum[x]+=sum[y]; unionn(lc[x],lc[y]); unionn(rc[x],rc[y]);}
把y合并到x上，如果y为0，那么自y一下都不用合并，
如果x为0，建立新的x
分析：合并思路正确，代码也正确，但做了大量无用的合并
如果x为0，新建一系列节点，这些节点完全等于y以下的节点，所以与y公用即可
错误合并2：
void unionn(int & x,int y){ if(!y) return; if(!x) x=y; else sum[x]+=sum[y]; unionn(lc[x],lc[y]); unionn(rc[x],rc[y]);}
思路错误，错误原因还不清楚
正确合并：
int unionn(int x,int y){ if(!x) return y; if(!y) return x; lc[x]=unionn(lc[x],lc[y]); rc[x]=unionn(rc[x],rc[y]); sum[x]=sum[lc[x]]+sum[rc[x]]; return x;}
自底向上的合并，公用节点
恕我无能，splay的没调出来
启发式合并复习
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。