2020-2021:teams:famerwzyyuki:左偏树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:famerwzyyuki:左偏树 [2020/05/24 21:56] yuki |
2020-2021:teams:famerwzyyuki:左偏树 [2020/05/24 22:42] (当前版本) yuki |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | 堆：\\ | + | **堆：**\\ |
| 完全二叉树，用数组模拟时，父亲节点的下标是儿子的$\frac{1}{2}$（整数部分）(同线段树)\\ | 完全二叉树，用数组模拟时，父亲节点的下标是儿子的$\frac{1}{2}$（整数部分）(同线段树)\\ | ||
| - | （以小根堆为例）根节点小于儿子节点。 | + | （以小根堆为例）根节点小于儿子节点。\\ |
| - | 操作： | + | 操作：\\ |
| - | 上浮：某个节点与其父亲比较，如果小于父亲就和父亲交换 | + | 上浮：某个节点与其父亲比较，如果小于父亲就和父亲交换\\ |
| - | 下沉：某个节点与两个儿子比较，若大于某个儿子与小的一个儿子交换 | + | 下沉：某个节点与两个儿子比较，若大于某个儿子与小的一个儿子交换\\ |
| - | 插入：插入到最后，然后上浮 | + | 插入：插入到最后，然后上浮\\ |
| - | 弹出：将根与最后一个点交换，再下沉。 | + | 弹出：将根与最后一个点交换，再下沉。\\ |
| ====== 左偏树： ====== | ====== 左偏树： ====== | ||
| 行 24: | 行 24: | ||
| 5.更新节点距离（右儿子+1）\\ | 5.更新节点距离（右儿子+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 | ||
| + | 1 5 4 2 3 | ||
| + | 1 1 5 | ||
| + | 1 2 5 | ||
| + | 2 2 | ||
| + | 1 4 2 | ||
| + | 2 2 | ||
| + | */ | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/famerwzyyuki/左偏树.1590328591.txt.gz · 最后更改: 2020/05/24 21:56 由 yuki
