2020-2021:teams:famerwzyyuki:左偏树

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:famerwzyyuki:左偏树 [2020/05/24 21:55]
yuki 创建
+++ 2020-2021:teams:famerwzyyuki:左偏树 [2020/05/24 22:42] (当前版本)
yuki
@@ 行 1: / 行 1: @@
-堆：\\
+**堆：**\\
-完全二叉树，用数组模拟时，父亲节点的下标是儿子的$frac{1}{2}$（整数部分）(同线段树)\\
+完全二叉树，用数组模拟时，父亲节点的下标是儿子的$\frac{1}{2}$（整数部分）(同线段树)\\
-（以小根堆为例）根节点小于儿子节点。
+（以小根堆为例）根节点小于儿子节点。\\
-操作：
+操作：\\
-上浮：某个节点与其父亲比较，如果小于父亲就和父亲交换
+上浮：某个节点与其父亲比较，如果小于父亲就和父亲交换\\
-下沉：某个节点与两个儿子比较，若大于某个儿子与小的一个儿子交换
+下沉：某个节点与两个儿子比较，若大于某个儿子与小的一个儿子交换\\
-插入：插入到最后，然后上浮
+插入：插入到最后，然后上浮\\
-弹出：将根与最后一个点交换，再下沉。
+弹出：将根与最后一个点交换，再下沉。\\
 ====== 左偏树： ======
@@ 行 24: / 行 24: @@
 .更新节点距离（右儿子+1）\\
-模板：
+<hidden 模板>
+<code cpp>
+#include<iostream>
+#include<cstdio>
+#include<cstring>
+#include<algorithm>
+#include<set>
+#include<queue>
+#include<vector>
+#include<cmath>
+#include<cstdlib>
+#include<map>
+#include<stack>
+using namespace std;
+const int N=100005;
+const int inf=0x3f3f3f3f;
+void getint(int&num){
+    char c;bool flag=0;num=0;
+    while((c=getchar())<'0'||c>'9')if(c=='-')flag=1;
+    while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
+    if(flag) num=-num;
+}
+int n,T,op,x,y,a[N],ch[N][2],fa[N],d[N];
+int merge(int x,int y){
+	if((!x)||(!y)) return x^y;
+	if(a[x]>a[y]) swap(x,y);
+	ch[x][1]=merge(ch[x][1],y);
+	fa[ch[x][1]]=x;
+	if(d[ch[x][1]]>d[ch[x][0]])
+		swap(ch[x][1],ch[x][0]);
+	d[x]=ch[x][1]?d[ch[x][1]+1]+1:0;
+	return x;
+}
+inline int root(int x){
+	while(fa[x]!=x)
+		x=fa[x];
+	return x;
+}
+inline void _pop(int x){
+	fa[ch[x][0]]=ch[x][0];
+	fa[ch[x][1]]=ch[x][1];
+	merge(ch[x][0],ch[x][1]);
+	ch[x][0]=ch[x][1]=fa[x]=d[x]=0,a[x]=-inf;
+}
+int main(){
+	getint(n),getint(T);
+	for(int i=1;i<=n;i++)
+		getint(a[i]),fa[i]=i;
+	while(T--){
+		getint(op),getint(x);
+		if(op==1){
+			getint(y);
+			if(a[x]==inf||a[y]==inf||x==y) continue ;
+			int s=root(x),t=root(y);
+			merge(s,t);
+		}
+		else{
+			if(a[x]==-inf){puts("-1");continue ;}
+			y=root(x),printf("%d\n",a[y]),_pop(y);
+		}
+	}
+}
+/*
+5
+5 4 2 3
+1 5
+2 5
+2
+4 2
+2
+*/
+</code>
+</hidden>

2020-2021/teams/famerwzyyuki/左偏树.1590328555.txt.gz · 最后更改: 2020/05/24 21:55 由 yuki