左偏树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <iostream>
#include <ctime>
#include <cstdio>
#include <cctype>
using namespace std;
const int maxn = 1e5+5;
struct Node
{
    int l,r,fa;     //l,r分别为左右儿子编号;fa为并查集,不属于左偏树，不属于左偏树，不属于左偏树!!!!,
    int val,dis;    //val为结点键值,val==-1代表结点被删除;dis为结点的距离
}ltt[maxn];         //内存池写法，与平衡树主席树相同
#define ls(x) ltt[x].l  //懒人专用define
#define rs(x) ltt[x].r
inline int merge(int x,int y)   //合并两堆，x,y都是堆顶元素的编号
{
    if(!x||!y) return x+y;  //如果有空的返回另一个，与fhq-Treap相同
    //? 或前语句是为了维护小根堆性质，或后语句是题目要求的（值相同则下标小的优先级高）
    if(ltt[x].val>ltt[y].val||(ltt[x].val==ltt[y].val&&x>y))
        std::swap(x,y);
    rs(x)=merge(rs(x),y);   //合并右子树和y，合并到右儿子上。
    ltt[rs(x)].fa=x;        //维护并查集，x的右儿子的父亲肯定是x，，，，右儿子可能在合并时发生变化，维护并查集
    if(ltt[ls(x)].dis<ltt[rs(x)].dis)   //如果不满足左偏树的性质了那就交换左右儿子
        std::swap(ls(x),rs(x));
    ltt[x].dis=ltt[rs(x)].dis+1;        //利用结点距离等于右儿子距离+1来更新dis
    return x;                           //return合并好后的堆顶结点编号，
}
int find(int x) { return ltt[x].fa==x?x:ltt[x].fa=find(ltt[x].fa); }    //并查集&&路径压缩
inline void pop(int x)  //删除堆顶元素
{
    ltt[x].val=-1;          //值置为-1代表被删除
    ltt[ls(x)].fa=ls(x);    //维护并查集（一个结点的父亲是结点本身，代表结点没有父亲了）
    ltt[rs(x)].fa=rs(x);    //维护并查集
//以上三步：删除堆顶，并维护左右儿子的并查集，使其没有父节点，就是在左偏树中删除了它，他们的父节点，是在左偏树中删除！！！




    //? 因为路径压缩，所以可能会有除了ls(x)和rs(x)以外的结点的fa指针指向x！！！！！！！！！！
    //? 所以要这样子写，不能让并查集断掉：
    //如果没有并查集：merge(ls(x),rs(x));即可
    ltt[x].fa=merge(ls(x),rs(x));
}
int main()
{

    int n,m;
    cin>>n>>m;
    ltt[0].dis=-1;//0号结点相当于NULL，即空结点，空结点距离=-1，见推论二
    for(int i=1;i<=n;i++)
    {
        cin>>ltt[i].val;  //读入值
        ltt[i].fa=i;        //初始化并查集
    }
    while(m--)
    {
        int opt,x,y;
        cin>>opt>>x;
        if(opt==1)
        {
            cin>>y;
            if(ltt[x].val==-1||ltt[y].val==-1)  //如果有一个被删除了
                continue;
            int fx=find(x),fy=find(y);          //利用并查集查找堆顶结点编号
            if(fx==fy) continue;                //如果已经在同一堆中
            ltt[fx].fa=ltt[fy].fa=merge(fx,fy); //合并
        }
        else
        {
            if(ltt[x].val==-1) cout<<-1<<endl;      //如果被删除了
            else
            {
                int fx = find(x);               //利用并查集查找堆顶结点编号
                cout<<ltt[fx].val<<endl;            //输出堆顶元素的值
                pop(fx);                        //并且弹出
            }
        }
    }
}