左偏树（p3377）

题目描述

如题，一开始有N个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：

操作1： 1 x y 将第x个数和第y个数所在的小根堆合并（若第x或第y个数已经被删除或第x和第y个数在用一个堆内，则无视此操作）

操作2： 2 x 输出第x个数所在的堆最小数，并将其删除（若第x个数已经被删除，则输出-1并无视删除操作）

输入格式

第一行包含两个正整数N、M，分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含N个正整数，其中第i个正整数表示第i个小根堆初始时包含且仅包含的数。

接下来M行每行2个或3个正整数，表示一条操作，格式如下：

操作1 ： 1 x y

操作2 ： 2 x

输出格式

输出包含若干行整数，分别依次对应每一个操作2所得的结果。

本题为左偏树模板题；我左偏树的第一题。

左偏树有合并，删除的操作。具体左偏树能做什么题，目前只知道有关合并的题，是可以用左偏树来做的，其他的以后再来补充。

在用左偏树的时候。

具体有三个框架

1.getf 即寻找祖先；

2.Merge 合并操作，如果是最小堆，则要满足x<y,最大堆反过来（这是我刚做这些题的时候的见解，目前认为就是这样）

然后进行合并的递归操作，最后则要满足左偏，即dis【x】>dis【y】；

　　　　　　　　　为什么要左偏？？？？？这可能是左偏树最重要的思想了；

　　　　　　　　左偏之后，能保证右边的深度较小，别人创造的这一算法里，是往右子树进行合并操作，操作的时间复杂度自然是按右子树的深度来算；

　　　　　　　　所以为了保证时间复杂度较小（logn）便要在右子树深度大于左子树时，交换两者的值；

3.pop操作，这个操作，是剔除堆中的最大值或者最小值，然后再将他的左右子树合并，其中一个成为新的根。然后再将被剔除点的父亲定为新根

为什么要定为新根呢，因为可能在下面的点中有直接指向这个点的节点。所以要将这些点指向新的。

 #include<cstdio>

 #include<algorithm>

 #include<string.h>

 #include<math.h>

 using namespace std;

 const int maxn=1e5+;

 int val[maxn];

 int f[maxn];

 int ch[maxn][];

 int dis[maxn];

 int getf(int x)  //标准并查集

 {

     if(f[x]==x) return x;

     else{

         f[x]=getf(f[x]);

         return f[x];

     }

 }

 int Merge(int x,int y)

 {

     if(!x||!y) return x+y;  //到底了；

     //保证最小堆性质     后面这个不懂

     if(val[x]>val[y]||(val[x]==val[y]&&x>y)) swap(x,y);

     //这个大概就是创这个算法的人的习惯了，将其定在右子树。

     //然后再在下面进行操作来满足偏左树的性质；

     ch[x][]=Merge(ch[x][],y);

     f[ch[x][]]=x;   //并查集操作；

     //满足偏左；

     if(dis[ch[x][]]<dis[ch[x][]]) swap(ch[x][],ch[x][]);

     //这个是偏左树的性质，想想就知道是对的。

     dis[x]=dis[ch[x][]]+;

     return x;

 }

 int main()

 {

     int n,m;

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++){

         scanf("%d",&val[i]);

         f[i]=i;

     }

     while(m--){

         int ope;

         scanf("%d",&ope);

         if(ope==){

             int t1,t2;

             scanf("%d%d",&t1,&t2);

             if(val[t1]==-||val[t2]==-) continue;

             t1=getf(t1);

             t2=getf(t2);

             if(t1==t2) continue;

             Merge(t1,t2);

         }

         else{

             int t;

             scanf("%d",&t);

             if(val[t]==-){

                 printf("-1\n");

                 continue;

             }

             t=getf(t);

             printf("%d\n",val[t]);

             //这里是pop的操作，将被T出的点定为-1；

             val[t]=-;

             //再将原本的根指向新根，让其他原本指向旧根的点能继续指向新根

             f[ch[t][]]=f[ch[t][]]=f[t]=Merge(ch[t][],ch[t][]);

             //将旧根的左右儿子以及dis清零

             ch[t][]=ch[t][]=dis[t]=;

         }

     }

     return ;

 }

巴特西

左偏树（p3377）

题目描述

输入格式

输出格式

最新文章

热门文章