题解 P3377 【【模板】左偏树（可并堆）】

不会被卡的可并堆——随机堆，了解一下！ 在合并时，随机与左子树或右子树合并即可。这样保证了左右子树的均匀，而且不需要频繁地交换左右儿子，无惧任何毒瘤数据。合并时间复杂度均摊$O(\log n)$。 ``` #include<cstdio> #include<cctype> #include<cstdlib> #include<algorithm> int Read() { int x=0; char c=getchar(); while(!isdigit(c)) c=getchar(); while(isdigit(c)) { x=x*10+(c^48); c=getchar(); } return x; }//普通的快读 int ch[100005][2],val[100005],fa[100005]; //这些东西和普通的二叉堆相同 int merge(int x,int y) { if (!x||!y) return x+y; if (val[x]>val[y]||(val[x]==val[y] && x>y)) std::swap(x,y); int opt=rand()&1;//注意这里，用随机数确定合并的方向 ch[x][opt]=merge(ch[x][opt],y); fa[ch[x][opt]]=x;//普通地维护并查集 return x; } int find(int x) { while(fa[x]) x=fa[x]; return x; } //比较坑的是不能路径压缩。如果路径压缩，一merge就会混乱。 void pop(int x) { val[x]=-1; fa[ch[x][0]]=fa[ch[x][1]]=0; merge(ch[x][0],ch[x][1]); }//普通的删除节点 int main() { srand(19260817);//普通的随机数种子 int n=Read(),m=Read(),x,y; for(int i=1; i<=n; i++) val[i]=Read(); while(m--) { if(Read()&1) { x=Read(),y=Read(); if(val[x]==-1||val[y]==-1||(x=find(x))==(y=find(y))) continue; merge(x,y); } else { x=Read(); if(val[x]==-1) puts("-1"); else { x=find(x); printf("%d\n",val[x]); pop(x); } } } return 0; } ```