[模板][P3377]左偏树

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]={-1},fa[mxn],f[mxn]; //勿忘记初始化dis[0]=-1

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]左偏树

Description：

Hint:

Solution:

最新文章

热门文章