首页 > 其他 > 详细

[P3377]左偏树

时间:2019-02-17 13:45:43      阅读:218      评论:0      收藏:0      [点我收藏+]

Description:

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

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

操作2: 2 x 输出第x个数所在的堆最小数,并将其删除(若第x个数已经被删除,则输出-1并无视删除操作)

Hint:

对于100%的数据:N<=100000,M<=100000

Solution:

模板题,详见代码

#include<bits/stdc++.h>
using namespace std;
const int mxn=1e5+5;
int n,m;
int ch[mxn][2],vis[mxn],val[mxn],dis[mxn],fa[mxn],f[mxn];

int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[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][1]=merge(ch[x][1],y); fa[ch[x][1]]=x;
    if(dis[ch[x][0]]<dis[ch[x][1]]) 
        swap(ch[x][0],ch[x][1]);
    dis[x]=dis[ch[x][1]]+1;
    return x;
}

void del(int x)
{
    vis[x]=1;
    fa[ch[x][0]]=ch[x][0],fa[ch[x][1]]=ch[x][1];
    fa[x]=merge(ch[x][0],ch[x][1]); //这里有个细节,由于路径压缩的存在,原树中的点可能指向删除节点,故需更新删除节点的fa[]
}

int main()
{
    scanf("%d%d",&n,&m); int opt,x,y;
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=n;++i) scanf("%d",&val[i]);
    for(int i=1;i<=m;++i) {
        scanf("%d",&opt);
        if(opt==1) {
            scanf("%d%d",&x,&y);
            if(vis[x]||vis[y]) continue ; //切记判断两点存在
            x=find(x),y=find(y);
            if(x!=y) //判断是否在一个堆
                merge(x,y);
        }
        else {
            scanf("%d",&x); 
            printf("%d\n",vis[x]==0?val[x=find(x)]:-1); //判断是否存在
            if(!vis[x]) del(x);
        }
    }
    
    return 0;
}

[P3377]左偏树

原文:https://www.cnblogs.com/list1/p/10390864.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!