[HDOJ1512 Monkey King]可合并堆

【算法分析】
据Lost天牛的所有算法总结所说，现在一般人能写得起有两种可合并堆，一种是左偏树，一种是斜堆。
然后斜堆好像算法是平摊的还是啥，单次可能变成O(n)@.@。。。
如果不是平摊只是期望的话。。。那么估计想二叉检索树一样对某些特殊数据会悲剧啊。。。
还是老老实实写左偏树比较好。
然后这题就是左偏树的模板题。
当然还要搞个并查集。
【其它】第一个左偏树。1Y
【CODE】
#include #include #include const int N=105555;
int n,m,fa[N];
struct Node{Node *l,*r;int key,dis;}sp[N],*root[N],*null;

void input(){
null=&sp[0];
for (int i=1;i<=n;i++){
scanf("%d",&sp[i].key);
fa[i]=i;
root[i]=&sp[i];
root[i]->dis=0;
root[i]->l=root[i]->r=null;
}
}

inline void swap(Node *&A,Node *&B){Node *tmp=A; A=B; B=tmp;}

int gf(int k){
if (fa[k]==k) return k;
else return fa[k]=gf(fa[k]);
}

Node* Union(Node *p,Node *q){
if (p==null) return q;
if (q==null) return p;
if (p->key p->r=Union(p->r,q);
if (p->l->dis if (p->r==null) p->dis=0;
else p->dis=p->r->dis+1;
return p;
}

void myself_c(Node *&R){
Node *lc=R->l,*rc=R->r;
R->key>>=1; R->l=R->r=null;
R=Union(R,lc);
R=Union(R,rc);
}

void work(){
scanf("%d",&m);
for (int x,y,i=1;i<=m;i++){
scanf("%d%d",&x,&y);
if (gf(x)==gf(y)) printf("-1n");
else{
myself_c(root[fa[x]]);
myself_c(root[fa[y]]);
root[fa[y]]=Union(root[fa[x]],root[fa[y]]);
fa[fa[x]]=fa[y];
printf("%dn",root[fa[y]]->key);
}
}
}

int main(){
while (scanf("%d",&n)!=EOF){
input();
work();
}
}