题意:链接方法:可并堆解析:来二中的第几天来着忘记了，讲了可并堆，于是去找裸题来刷。对于合并操作，如果有一个为空则根为另一个。然后我们不妨假设x键值小于y。那么由于左偏树的左右子树同为左偏树，，所以整个过程就形成了个递归即把x的右子树再与y为根的子树合并。合并后维护左偏，即保证NPL的左比右大。之后再更新根节点的NPL。其实以上就是合并的全过程，只是叙述一遍加深记忆而已。代码:;int ch[N][2],h[N],key[N],fa[N];bool col[N];int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}int merge(int x,int y){if(!x)return y;if(!y)return x;if(key[y]<key[x])swap(x,y);ch[x][1]=merge(ch[x][1],y);if(h[ch[x][1]]>h[ch[x][0]])swap(ch[x][0],ch[x][1]);if(!h[ch[x][1]])h[x]=0;else h[x]=h[ch[x][1]]+1;return x;}int n,q;char s[5];int main(){scanf(“%d”,&n);for(int i=1;i<=n;i++)scanf(“%d”,&key[i]);for(int i=1;i<=n;i++)fa[i]=i;h[0]=-1;scanf(“%d”,&q);for(int i=1;i<=q;i++){scanf(“%s”,s);if(s[0]==’M’){int x,y;scanf(“%d%d”,&x,&y);if(col[x]||col[y])continue;int fx=find(x),fy=find(y);if(fx!=fy){int t=merge(fx,fy);fa[fx]=t,fa[fy]=t;}}else{int x;scanf(“%d”,&x);if(col[x])printf(“%d\n”,0);else{int fx=find(x);col[fx]=1;printf(“%d\n”,key[fx]);fa[fx]=merge(ch[fx][0],ch[fx][1]);fa[fa[fx]]=fa[fx];}}}}
强者能同命运的风暴抗争。
