题目描述 https://www.luogu.org/problemnew/show/P3377
题解:
左偏树, 一棵向左倾斜的二叉树.
板子:
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- const int N = 100050;
- template<typename T>
- inline void read(T&x)
- {
- T f = 1,c = 0;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
- x = f*c;
- }
- int n,m,fa[N],v[N],dis[N],ls[N],rs[N];
- int merge(int x,int y)
- {
- if(!x||!y)return x+y;
- if(v[x]>v[y]||(v[x]==v[y]&&x>y))swap(x,y);
- rs[x] = merge(rs[x],y);
- fa[rs[x]] = x;
- if(dis[ls[x]]<dis[rs[x]])swap(ls[x],rs[x]);
- dis[x] = dis[rs[x]]+1;
- return x;
- }
- int get_top(int x)
- {
- while(fa[x])x=fa[x];
- return x;
- }
- int erase(int x)
- {
- if(fa[x]==-1)return -1;
- x = get_top(x);
- fa[x] = -1;
- int u = merge(ls[x],rs[x]);
- fa[u] = 0;
- return v[x];
- }
- int main()
- {
- read(n),read(m);
- for(int i=1;i<=n;i++)
- {
- read(v[i]);
- dis[i] = 1;
- }
- for(int opt,x,y,i=1;i<=m;i++)
- {
- read(opt);
- if(opt==1)
- {
- read(x),read(y);
- if(fa[x]==-1||fa[y]==-1)continue;
- int tx = get_top(x),ty = get_top(y);
- if(tx==ty)continue;
- int u = merge(tx,ty);
- fa[u] = 0;
- }else
- {
- read(x);
- printf("%d\n",erase(x));
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2927819.html