LUOGU 3377 左偏树

Description

如题，一开始有个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：
操作1 将第x个数和第y个数所在的小根堆合并（若第x或第y个数已经被删除或第x和第y个数在用一个堆内，则无视此操作）
操作2 输出第x个数所在的堆最小数，并将其删除（若第x个数已经被删除，则输出-1并无视删除操作）

Input Format

第一行包含两个正整数，分别表示一开始小根堆的个数和接下来操作的个数。
第二行包含个正整数，其中第个正整数表示第个小根堆初始时包含且仅包含的数。
接下来行每行个或个正整数，表示一条操作，格式如下：
操作1
操作2

Output Format

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

Sample Input

5 5
1 5 4 2 3
1 1 5
1 2 5
2 2
1 4 2
2 2

Sample Output

1
2

Constraints

对于%的数据：

CCYOS

这是一道左偏树板子题。感谢徐灏诚juju的讲课，挺好理解的。

1. 左偏树
   可并堆的一种，有如下性质：
   a.堆性质
   保证每颗子树的根节点的权值小于它的左儿子和右儿子的权值，这样可以删除本堆中的最小节点。
   b.左偏性质
   定义有一颗子树为空的节点为外节点。
   定义每个点的为这个点到它的后代中的外节点的最短距离。
   左偏树满足但是这并不代表左偏树左子树比右子树深度大
   所以有不可能会出现单右子树的情况，所以令来使下图的根（外节点）的正确。 权值为5的节点的dist为0

2)左偏树的合并
设有两棵左偏树需要合并。
左偏树的合并是努力让B和A的右子树合并，简称把我的兄弟（？）变成我的儿子，同时要维护左偏树的性质。
a.有一棵树为空：直接返回该子树。

if(!x||!y)return x + y;

b.没有空子树：
为了维护堆性质，选取中根节点权值较小的左偏树作为树。
向下合并，将的右儿子和合并的树的根节点作为的右儿子。
为了维护左偏性质，若左儿子的值小于右儿子的值，交换左右儿子。
更新树根节点的及左右儿子的。
返回合并完毕的左偏树。

inline int Merge(int x,int y){
    if(!x || !y)return x + y;
    if(tr[x].val > tr[y].val)swap(x,y);
    if(tr[x].val == tr[y].val && x > y)swap(x,y);
    rs = Merge(rs,y);
    if(tr[ls].dis < tr[rs].dis)swap(ls,rs);
    tr[ls].rt = tr[rs].rt = tr[x].rt = x;
    tr[x].dis = tr[rs].dis + 1;
    return x;
}

3. 左偏树的删除
   仅限于删除最小节点。
   删除最小节点，重置左右儿子的根，合并左右儿子。

inline void Pop(int x){
    tr[x].val = -1;
    tr[ls].rt = ls;tr[rs].rt = rs;
    tr[x].rt = Merge(ls,rs);
}

注意
a) Merge(rs,y)要更新给rs。
b) 注意题目要求的输出。
c) tr[0].dist = -1。
code

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;

int N,M;

struct tree{
    int Ls,Rs,rt,val,dis;
}tr[100005];

inline int read(){
    int ret = 0,fl = 1;
    char c = getchar();
    for(;!isdigit(c)&&c != '-';c = getchar())if(c == '-')fl = 0;
    for(;isdigit(c);c = getchar())ret = (ret << 3) + (ret << 1) + c - 48;
    return fl ? ret : -ret;
}

#define ls tr[x].Ls
#define rs tr[x].Rs
inline int findf(int x){return tr[x].rt == x ? x : tr[x].rt = findf(tr[x].rt);}

inline int Merge(int x,int y){
    if(!x || !y)return x + y;
    if(tr[x].val > tr[y].val)swap(x,y);
    if(tr[x].val == tr[y].val && x > y)swap(x,y);
    rs = Merge(rs,y);
    if(tr[ls].dis < tr[rs].dis)swap(ls,rs);
    tr[ls].rt = tr[rs].rt = tr[x].rt = x;
    tr[x].dis = tr[rs].dis + 1;
    return x;
}

inline void Pop(int x){
    tr[x].val = -1;
    tr[ls].rt = ls;tr[rs].rt = rs;
    tr[x].rt = Merge(ls,rs);
}

int main(){
//  freopen("testdata.in","r",stdin);
//  freopen("testdata.out","w",stdout);

    N = read();M = read();tr[0].dis = -1;
    for(register int i = 1;i <= N;++i)
        tr[i].val = read(),tr[i].rt = i;
    for(register int i = 1;i <= M;++i){
        int op = read();
        if(op == 1){
            int x = read();int y = read();
            if(tr[x].val == -1||tr[y].val == -1)continue;
            x = findf(x);y = findf(y);
            if(x == y)continue;
            tr[x].rt = tr[y].rt = Merge(x,y);
        }
        else{
            int x = read();
            if(tr[x].val == -1)printf("-1\n");
            else{
                x = findf(x);
                printf("%d\n",tr[x].val);Pop(x);
            }
        }
    }
    return 0;
}