要求维护一个数据结构,支持:
(1)一开始有n个集合,每个集合内一个元素
(2)合并两个集合
(3)询问一个集合内元素的最小值,并删除
裸的可并堆。
第一次尝试写斜堆。斜堆代码很短,时间复杂度也有保证。(均摊logn)。
这道题是小根堆。key[A]表示A堆的堆顶最小值。
int Merge(A,B):先保证key[A]<=key[B]。然后Merge(A的右子树,B),递归进行。然后交换A的左右子树。最后返回A。
找根什么的用并查集维护。
删除堆顶元素的时候,只要Merge它的两个子树就好了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1000010; int rt[maxn],ls[maxn]={0},rs[maxn]={0},key[maxn],fa[maxn],d[maxn]={0};char op[2]; int getfa(int x){ return x==fa[x] ? x : fa[x] = getfa(fa[x]); }int merge(int a,int b){ if(!a || !b) return a+b; if(key[a] > key[b]) swap(a,b); rs[a] = merge(rs[a],b); swap(ls[a],rs[a]); return a; }int main(){ int n,q,x,y; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&key[fa[i]=i]); scanf("%d",&q); while(q--){ scanf("%s",op); if(op[0]=='M'){ scanf("%d%d",&x,&y); if(d[x] || d[y]) continue; x = getfa(x); y = getfa(y); if(x == y) continue; fa[x] = fa[y] = merge(x,y); }else{ scanf("%d",&x); if(d[x]){ printf("0\n"); continue;} d[x = getfa(x)] = 1; printf("%d\n",key[x]); fa[x] = merge(ls[x],rs[x]); fa[fa[x]] = fa[x]; } }return 0; }