一种均摊复杂度很低的可并堆...

https://oi-wiki.org/ds/pairing-heap/

据说常数 / 理解难易度吊打几种常见堆... 虽然我太蒻还不知道斐波那契堆是个啥玩意 qwq

核心操作是 merge... 但最复杂的操作是 delete...

还可以改值... 但我也不知道怎么改...（加上改值的操作的话就难上不少）
（PS：根据维基，配对堆改值的复杂度 $\log n$，但是有个 Rank-paring Heaps 可以做到 $O(1)$ 改值，不过国内没有相关中文资料。）（2020-10-5 upd: 现在有了。https://etaoinwu.com/blog/pairing-heaps-and-rank-pairing-heaps/）

这里想要说的话就是这玩意套到洛谷模板上去可能比较难打
原因就是洛谷模板上需要维护所属堆
而对于本堆来说，直接迭代查找父亲的话有点 emmm

所以这里提供了一种路径压缩的方案...

不在内存中删去该点... 将被删去的点的父亲指向新堆的根...
这样子的话就可以路径压缩了...
主要问题就是父指针要清干净...

关于效率问题，比我手写的指针左偏树快上一倍...
但是还是没有其他 dalao 写的好... 大概是递归和指针还有大量函数调用的原因吧...

反正，也挺优秀了不是吗 qwq

Code

#include<bits/stdc++.h>
using namespace std;

inline void gn(int &x) {
    register char ch=getchar(); x=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar();
}

const int N=1e5+10;
struct Node *nil;
struct Node {
    int v, v2, d;
    Node *ls, *rs, *f;
    Node(register int val=-0x3f3f3f3f, register int val2=-0x3f3f3f3f) { v=val, v2=val2, d=0; f=ls=rs=nil; }
} rt[N];

Node * merge(Node *a, Node *b) {
    if(a==nil || b==nil || a==b) return a==nil?b:a;
    if(a->v>b->v || (a->v==b->v && a->v2>b->v2)) swap(a, b);
    b->rs=a->ls, a->ls=b, b->f=a, a->f=nil;
    return a;
}

Node * merges(Node *x) {
    if(x==nil) return x;
    Node *xr=x->rs, *xrr=xr->rs;
    x->rs=xr->rs=x->f=xr->f=nil;
    return merge(merge(x, xr), merges(xrr));
}

Node * find(Node *x) {
    return x->f!=nil?x->f=find(x->f):x;
}

int main() {
    nil=new Node, nil->ls=nil->rs=nil->f=nil;
    int cmd, a, b, n, m;
    gn(n), gn(m);
    for(int i=1; i<=n; i++) gn(a), rt[i]=Node(a, i);
    while(m--) {
        gn(cmd);
        if(cmd==1) {
            gn(a), gn(b);
            if(!rt[a].d && !rt[b].d) merge(find(&rt[a]), find(&rt[b]));
        }
        else if(cmd==2) {
            gn(a);
            if(rt[a].d) puts("-1");
            else {
                register Node *nd=find(&rt[a]);
                printf("%d\n", nd->v), nd->d=1, nd->f=merges(nd->ls);
            }
        }
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/pairing_heaps.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆