题解 P3377 【【模板】左偏树（可并堆）】

SuperJvRuo · 2018-07-24 19:36:14 · 题解

不会被卡的可并堆——随机堆，了解一下！

在合并时，随机与左子树或右子树合并即可。这样保证了左右子树的均匀，而且不需要频繁地交换左右儿子，无惧任何毒瘤数据。合并时间复杂度均摊O(\log n)。

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<algorithm>

int Read()
{
    int x=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        x=x*10+(c^48);
        c=getchar();
    }
    return x;
}//普通的快读

int ch[100005][2],val[100005],fa[100005];
//这些东西和普通的二叉堆相同

int merge(int x,int y)
{
    if (!x||!y)
        return x+y;
    if (val[x]>val[y]||(val[x]==val[y] && x>y))
        std::swap(x,y);
    int opt=rand()&1;//注意这里，用随机数确定合并的方向
    ch[x][opt]=merge(ch[x][opt],y);
    fa[ch[x][opt]]=x;//普通地维护并查集
    return x;
}

int find(int x)
{
    while(fa[x])
        x=fa[x];
    return x;
}
//比较坑的是不能路径压缩。如果路径压缩，一merge就会混乱。

void pop(int x)
{
    val[x]=-1;
    fa[ch[x][0]]=fa[ch[x][1]]=0;
    merge(ch[x][0],ch[x][1]);
}//普通的删除节点

int main()
{
    srand(19260817);//普通的随机数种子
    int n=Read(),m=Read(),x,y;
    for(int i=1; i<=n; i++)
        val[i]=Read();
    while(m--)
    {
        if(Read()&1)
        {
            x=Read(),y=Read();
            if(val[x]==-1||val[y]==-1||(x=find(x))==(y=find(y)))
                continue;
            merge(x,y);
        }
        else
        {
            x=Read();
            if(val[x]==-1)
                puts("-1");
            else
            {
                x=find(x);
                printf("%d\n",val[x]);
                pop(x);
            }
        }
    }
    return 0;
}